本書圖文并茂、通俗易懂，詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)階知識(shí)，并融入大量的競(jìng)賽實(shí)例和解題技巧，可幫助讀者領(lǐng)悟數(shù)據(jù)結(jié)構(gòu)和算法的精髓，并熟練應(yīng)用其解決實(shí)際問題。 本書總計(jì)8章。第1章講解數(shù)據(jù)結(jié)構(gòu)進(jìn)階知識(shí)，涉及分塊算法和跳躍表；第2章講解字符串算法進(jìn)階知識(shí)，涉及AC自動(dòng)機(jī)和后綴數(shù)組；第3章講解樹上操作，涉及樹鏈剖分、點(diǎn)分治和邊分治；第4章講解復(fù)雜樹，涉及KD樹、左偏樹、動(dòng)態(tài)樹和樹套樹；第5章講解可持久化數(shù)據(jù)結(jié)構(gòu)，涉及可持久化線段樹和可持久化字典樹；第6章講解圖論算法進(jìn)階知識(shí)，涉及EK算法、Dinic算法、ISAP算法、二分圖匹配、最大流最小割和最小費(fèi)用最大流；第7章講解動(dòng)態(tài)規(guī)劃進(jìn)階知識(shí)，涉及背包問題進(jìn)階知識(shí)和樹形DP進(jìn)階知識(shí)；第8章講解復(fù)雜動(dòng)態(tài)規(guī)劃及其優(yōu)化，涉及數(shù)位DP、插頭DP、斜率優(yōu)化和四邊不等式優(yōu)化。
陳小玉高級(jí)程序員，主要研究方向?yàn)樗惴▋?yōu)化和機(jī)器學(xué)習(xí)。出版著作有《趣學(xué)算法》《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》《算法訓(xùn)練營》，所教學(xué)生多次獲得ACM-ICPC、藍(lán)橋杯等算法競(jìng)賽獎(jiǎng)項(xiàng)。
第1章 數(shù)據(jù)結(jié)構(gòu)進(jìn)階 1
1.1 分塊算法 1
1.1.1 預(yù)處理 2
1.1.2 區(qū)間更新 2
1.1.3 區(qū)間查詢 3
訓(xùn)練1 超級(jí)馬里奧 4
訓(xùn)練2 序列操作 7
1.2 跳躍表 9
1.2.1 跳躍表的結(jié)構(gòu)體定義 11
1.2.2 查找 12
1.2.3 插入 13
1.2.4 刪除 14
訓(xùn)練1 第k大的數(shù) 15
訓(xùn)練2 郁悶的出納員 21
第2章 字符串算法進(jìn)階 24
2.1 AC自動(dòng)機(jī) 24
2.1.1 創(chuàng)建字典樹 24
2.1.2 創(chuàng)建AC自動(dòng)機(jī) 25
2.1.3 模式匹配 27
訓(xùn)練1 病毒侵襲 28
訓(xùn)練2 DNA序列 30
2.2 后綴數(shù)組 34
2.2.1 基數(shù)排序 34
2.2.2 后綴數(shù)組詳解 41
2.2.3 后綴數(shù)組的應(yīng)用 50
訓(xùn)練1 牛奶模式 57
訓(xùn)練2 音樂主題 60
第3章 樹上操作 62
3.1 樹鏈剖分 62
3.1.1 預(yù)處理 63
3.1.2 求解最近公共祖先 63
3.1.3 樹鏈剖分與線段樹 66
訓(xùn)練1 樹上距離 71
訓(xùn)練2 樹上操作 73
3.2 點(diǎn)分治 76
3.2.1 樹的重心 76
3.2.2 重心分解 77
訓(xùn)練1 樹上兩個(gè)節(jié)點(diǎn)之間的路徑數(shù) 77
訓(xùn)練2 游船之旅 83
3.3 邊分治 88
3.3.1 重建樹 88
3.3.2 求解中心邊 89
3.3.3 中心邊分解 90
訓(xùn)練1 樹上查詢 91
訓(xùn)練2 樹上兩個(gè)節(jié)點(diǎn)之間的路徑數(shù) 100
第4章 復(fù)雜樹 104
4.1 KD樹 104
4.1.1 創(chuàng)建KD樹 104
4.1.2 搜索m近鄰 106
訓(xùn)練1 最近的取款機(jī) 107
訓(xùn)練2 最近鄰m點(diǎn) 110
4.2 左偏樹 112
4.2.1 左偏樹的性質(zhì) 112
4.2.2 基本操作 114
訓(xùn)練1 猴王 120
訓(xùn)練2 小根堆 123
4.3 動(dòng)態(tài)樹 125
4.3.1 LCT的性質(zhì) 126
4.3.2 LCT的基本操作 127
訓(xùn)練1 動(dòng)態(tài)樹的異或和 136
訓(xùn)練2 動(dòng)態(tài)樹的最值 139
4.4 樹套樹 142
4.4.1 線段樹套平衡樹 142
4.4.2 線段樹套線段樹 143
訓(xùn)練1 動(dòng)態(tài)區(qū)間問題 143
訓(xùn)練2 打馬賽克 149
第5章 可持久化數(shù)據(jù)結(jié)構(gòu) 156
5.1 可持久化線段樹 156
訓(xùn)練1 超級(jí)馬里奧 163
訓(xùn)練2 記憶重現(xiàn) 167
5.2 可持久化字典樹 172
訓(xùn)練 最大異或和 173
第6章 圖論算法進(jìn)階 180
6.1 EK算法 183
訓(xùn)練 排水系統(tǒng) 188
6.2 Dinic算法 188
訓(xùn)練 電力網(wǎng)絡(luò) 193
6.3 ISAP算法 195
訓(xùn)練 美味佳肴 200
6.4 二分圖匹配 201
6.4.1 最大匹配算法 202
6.4.2 匈牙利算法 202
訓(xùn)練1 完美的牛棚 206
訓(xùn)練2 逃脫 207
6.5 最大流最小割 208
訓(xùn)練1 最小邊割集 210
訓(xùn)練2 最小點(diǎn)割集 211
訓(xùn)練3 最大收益 213
6.6 最小費(fèi)用最大流 214
訓(xùn)練1 農(nóng)場(chǎng)之旅 218
訓(xùn)練2 航空路線 219
第7章 動(dòng)態(tài)規(guī)劃進(jìn)階 222
7.1 背包問題進(jìn)階 222
7.1.1 多重背包問題 222
訓(xùn)練 硬幣 224
7.1.2 分組背包問題 227
訓(xùn)練 價(jià)值最大化 228
7.1.3 混合背包問題 229
訓(xùn)練 最少硬幣 230
7.2 樹形DP進(jìn)階 232
7.2.1 背包類樹形DP 232
訓(xùn)練1 城堡中的寶物 232
訓(xùn)練2 蘋果樹 235
7.2.2 不定根樹形DP 238
訓(xùn)練1 最大累積度 239
訓(xùn)練2 最遠(yuǎn)距離 243
第8章 復(fù)雜動(dòng)態(tài)規(guī)劃及其
優(yōu)化 247
8.1 數(shù)位DP 247
訓(xùn)練1 不吉利的數(shù)字 247
訓(xùn)練2 定時(shí)炸彈 253
8.2 插頭DP 255
訓(xùn)練1 鋪磚 256
訓(xùn)練2 多回路連通性問題 262
8.3 斜率優(yōu)化 266
訓(xùn)練1 打印文章 266
訓(xùn)練2 批處理作業(yè) 270
8.4 四邊不等式優(yōu)化 275
訓(xùn)練 劃分 277
書單推薦
