算法訓練營：進階篇（全彩版）

第1章 數據結構進階 1
1.1 分塊算法 1
1.1.1 預處理 2
1.1.2 區間更新 2
1.1.3 區間查詢 3
訓練1 超級馬里奧 4
訓練2 序列操作 7
1.2 跳躍表 9
1.2.1 跳躍表的結構體定義 11
1.2.2 查找 12
1.2.3 插入 13
1.2.4 刪除 14
訓練1 第k大的數 15
訓練2 鬱悶的出納員 21
第2章 字符串算法進階 24
2.1 AC自動機 24
2.1.1 創建字典樹 24
2.1.2 創建AC自動機 25
2.1.3 模式匹配 27
訓練1 病毒侵襲 28
訓練2 DNA序列 30
2.2 後綴數組 34
2.2.1 基數排序 34
2.2.2 後綴數組詳解 41
2.2.3 後綴數組的應用 50
訓練1 牛奶模式 57
訓練2 音樂主題 60
第3章 樹上操作 62
3.1 樹鏈剖分 62
3.1.1 預處理 63
3.1.2 求解最近公共祖先 63
3.1.3 樹鏈剖分與線段樹 66
訓練1 樹上距離 71
訓練2 樹上操作 73
3.2 點分治 76
3.2.1 樹的重心 76
3.2.2 重心分解 77
訓練1 樹上兩個節點之間的路徑數 77
訓練2 游船之旅 83
3.3 邊分治 88
3.3.1 重建樹 88
3.3.2 求解中心邊 89
3.3.3 中心邊分解 90
訓練1 樹上查詢 91
訓練2 樹上兩個節點之間的路徑數 100
第4章 復雜樹 104
4.1 KD樹 104
4.1.1 創建KD樹 104
4.1.2 搜索m近鄰 106
訓練1 最近的取款機 107
訓練2 最近鄰m點 110
4.2 左偏樹 112
4.2.1 左偏樹的性質 112
4.2.2 基本操作 114
訓練1 猴王 120
訓練2 小根堆 123
4.3 動態樹 125
4.3.1 LCT的性質 126
4.3.2 LCT的基本操作 127
訓練1 動態樹的異或和 136
訓練2 動態樹的最值 139
4.4 樹套樹 142
4.4.1 線段樹套平衡樹 142
4.4.2 線段樹套線段樹 143
訓練1 動態區間問題 143
訓練2 打馬賽克 149
第5章 可持久化數據結構 156
5.1 可持久化線段樹 156
訓練1 超級馬里奧 163
訓練2 記憶重現 167
5.2 可持久化字典樹 172
訓練 最大異或和 173
第6章 圖論算法進階 180
6.1 EK算法 183
訓練 排水系統 188
6.2 Dinic算法 188
訓練 電力網絡 193
6.3 ISAP算法 195
訓練 美味佳餚 200
6.4 二分圖匹配 201
6.4.1 最大匹配算法 202
6.4.2 匈牙利算法 202
訓練1 完美的牛棚 206
訓練2 逃脫 207
6.5 最大流最小割 208
訓練1 最小邊割集 210
訓練2 最小點割集 211
訓練3 最大收益 213
6.6 最小費用最大流 214
訓練1 農場之旅 218
訓練2 航空路線 219
第7章 動態規劃進階 222
7.1 背包問題進階 222
7.1.1 多重背包問題 222
訓練 硬幣 224
7.1.2 分組背包問題 227
訓練 價值最大化 228
7.1.3 混合背包問題 229
訓練 最少硬幣 230
7.2 樹形DP進階 232
7.2.1 背包類樹形DP 232
訓練1 城堡中的寶物 232
訓練2 蘋果樹 235
7.2.2 不定根樹形DP 238
訓練1 最大累積度 239
訓練2 最遠距離 243
第8章 復雜動態規劃及其
優化 247
8.1 數碼DP 247
訓練1 不吉利的數字 247
訓練2 定時炸彈 253
8.2 插頭DP 255
訓練1 鋪磚 256
訓練2 多迴路連通性問題 262
8.3 斜率優化 266
訓練1 打印文章 266
訓練2 批處理作業 270
8.4 四邊不等式優化 275
訓練 劃分 277