第1章 實(shí)用數(shù)據(jù)結(jié)構(gòu) 1
1.1 并查集 1
原理 并查集詳解 1
訓(xùn)練1 暢通工程 6
訓(xùn)練2 方塊棧 7
訓(xùn)練3 食物鏈 10
訓(xùn)練4 幫派 16
1.2 優(yōu)先隊(duì)列 19
原理1 優(yōu)先隊(duì)列的實(shí)現(xiàn)原理 19
原理2 優(yōu)先隊(duì)列詳解 23
訓(xùn)練1 第k大的數(shù) 26
訓(xùn)練2 圍欄修復(fù) 27
訓(xùn)練3 表演評(píng)分 29
訓(xùn)練4 叢林探險(xiǎn) 30

第2章 區(qū)間信息維護(hù)與查詢 33
2.1 倍增、ST、RMQ 33
原理1 倍增 33
原理2 ST 34
原理3 RMQ 36
訓(xùn)練1 區(qū)間最值差 36
訓(xùn)練2 最頻繁值 37
訓(xùn)練3 最小分段數(shù) 40
訓(xùn)練4 二維區(qū)間最值差 41
2.2 最近公共祖先LCA 43
原理1 暴力搜索法 44
原理2 樹(shù)上倍增法 45
原理3 在線RMQ算法 49
原理4 Tarjan算法 51
訓(xùn)練1 最近公共祖先 55
訓(xùn)練2 樹(shù)上距離 57
訓(xùn)練3 距離查詢 59
訓(xùn)練4 城市之間的聯(lián)系 60
2.3 樹(shù)狀數(shù)組 62
原理1 一維樹(shù)狀數(shù)組 62
原理2 多維樹(shù)狀數(shù)組 67
訓(xùn)練1 數(shù)星星 69
訓(xùn)練2 公路交叉數(shù) 71
訓(xùn)練3 子樹(shù)查詢 74
訓(xùn)練4 矩形區(qū)域查詢 76
2.4 線段樹(shù) 78
原理1 線段樹(shù)的基本操作 78
原理2 線段樹(shù)中的“懶操作” 83
訓(xùn)練1 敵兵布陣 87
訓(xùn)練2 簡(jiǎn)單的整數(shù)問(wèn)題 89
訓(xùn)練3 數(shù)據(jù)結(jié)構(gòu)難題 91
訓(xùn)練4 顏色統(tǒng)計(jì) 97
2.5 分塊 102
原理 分塊詳解 102
訓(xùn)練1 簡(jiǎn)單的整數(shù)問(wèn)題 105
訓(xùn)練2 數(shù)字序列 106
訓(xùn)練3 區(qū)間最值差 107
訓(xùn)練4 超級(jí)馬里奧 109
訓(xùn)練5 序列操作 111

第3章 字符串處理 115
3.1 字典樹(shù) 115
原理 字典樹(shù)詳解 115
訓(xùn)練1 單詞翻譯 120
訓(xùn)練2 電話表 122
訓(xùn)練3 統(tǒng)計(jì)難題 123
訓(xùn)練4 彩色的木棒 124
訓(xùn)練5 最長(zhǎng)xor路徑 127
3.2 AC自動(dòng)機(jī) 129
原理 AC自動(dòng)機(jī)詳解 129
訓(xùn)練1 關(guān)鍵字檢索 132
訓(xùn)練2 病毒侵襲 134
訓(xùn)練3 DNA序列 136
訓(xùn)練4 單詞情結(jié) 140
3.3 后綴數(shù)組 145
原理1 基數(shù)排序 145
原理2 后綴數(shù)組詳解 152
訓(xùn)練1 牛奶模式 169
訓(xùn)練2 口吃的外星人 171
訓(xùn)練3 音樂(lè)主題 173
訓(xùn)練4 星際迷航 175

第4章 樹(shù)上操作 178
4.1 點(diǎn)分治 178
原理 重心分解 178
訓(xùn)練1 樹(shù)上兩點(diǎn)之間的路徑數(shù) 179
訓(xùn)練2 游船之旅 185
訓(xùn)練3 摩天大樹(shù) 189
訓(xùn)練4 查詢子樹(shù) 194
4.2 邊分治 200
原理 邊分治詳解 200
訓(xùn)練1 樹(shù)上查詢I 203
訓(xùn)練2 樹(shù)上查詢II 212
訓(xùn)練3 樹(shù)上兩點(diǎn)之間的路徑數(shù) 217
4.3 樹(shù)鏈剖分 221
原理 樹(shù)鏈剖分詳解 221
訓(xùn)練1 樹(shù)上距離 230
訓(xùn)練2 樹(shù)的統(tǒng)計(jì) 231
訓(xùn)練3 家庭主婦 232
訓(xùn)練4 樹(shù)上操作 233
4.4 動(dòng)態(tài)樹(shù) 236
原理 動(dòng)態(tài)樹(shù)詳解 236
訓(xùn)練1 距離查詢 247
訓(xùn)練2 動(dòng)態(tài)樹(shù)xor和 249
訓(xùn)練3 動(dòng)態(tài)樹(shù)的最值 252
訓(xùn)練4 動(dòng)態(tài)樹(shù)的第2大值 255
訓(xùn)練5 樹(shù)上操作 261

第5章 平衡二叉樹(shù) 263
5.1 Treap 263
原理 Treap詳解 263
訓(xùn)練1 雙重隊(duì)列 270
訓(xùn)練2 普通平衡樹(shù) 272
訓(xùn)練3 黑盒子 276
訓(xùn)練4 少林功夫 279
5.2 伸展樹(shù) 283
原理 伸展樹(shù)詳解 283
訓(xùn)練1 雙重隊(duì)列 291
訓(xùn)練2 玩鏈子 293
訓(xùn)練3 超強(qiáng)記憶 300
訓(xùn)練4 循環(huán) 310
5.3 SBT 324
原理 SBT詳解 324
訓(xùn)練1 雙重隊(duì)列 331
訓(xùn)練2 第k小的數(shù) 333
訓(xùn)練3 第k大的數(shù) 334
訓(xùn)練4 區(qū)間第k小 334
訓(xùn)練5 郁悶的出納員 336

第6章 數(shù)據(jù)結(jié)構(gòu)進(jìn)階 339
6.1 KD樹(shù) 339
原理 KD樹(shù)詳解 339
訓(xùn)練1 最近的取款機(jī) 343
訓(xùn)練2 找旅館 346
訓(xùn)練3 最近鄰M點(diǎn) 348
訓(xùn)練4 蟻巢 349
6.2 左偏樹(shù) 352
原理 左偏樹(shù)詳解 352
訓(xùn)練1 猴王 360
訓(xùn)練2 小根堆 363
訓(xùn)練3 路面修整 365
訓(xùn)練4 K-單調(diào) 369
6.3 跳躍表 373
原理 跳躍表詳解 373
訓(xùn)練1 雙重隊(duì)列 379
訓(xùn)練2 第k大的數(shù) 381
訓(xùn)練3 郁悶的出納員 386
6.4 樹(shù)套樹(shù) 388
原理 樹(shù)套樹(shù)詳解 388
訓(xùn)練1 動(dòng)態(tài)區(qū)間問(wèn)題 389
訓(xùn)練2 動(dòng)態(tài)區(qū)間第k小 395
訓(xùn)練3 矩形區(qū)域查詢 396
訓(xùn)練4 馬賽克處理 400
6.5 可持久化數(shù)據(jù)結(jié)構(gòu) 406
原理1 可持久化線段樹(shù)詳解 406
原理2 可持久化Trie詳解 413
訓(xùn)練1 超級(jí)馬里奧 415
訓(xùn)練2 記憶重現(xiàn) 419
訓(xùn)練3 最大異或和 424

第7章 動(dòng)態(tài)規(guī)劃及其優(yōu)化 431
7.1 動(dòng)態(tài)規(guī)劃求解原理 431
原理1 動(dòng)態(tài)規(guī)劃的三個(gè)要素 432
原理2 動(dòng)態(tài)規(guī)劃設(shè)計(jì)方法 432
7.2 背包問(wèn)題 433
原理1 01背包 433
訓(xùn)練1 骨頭收藏家 441
原理2 完全背包 443
訓(xùn)練2 存錢罐 443
原理3 多重背包 445
訓(xùn)練3 硬幣 447
原理4 分組背包 449
訓(xùn)練4 價(jià)值最大化 450
原理5 混合背包 452
訓(xùn)練5 最少的硬幣 452
7.3 線性DP 455
訓(xùn)練1 超級(jí)樓梯 455
訓(xùn)練2 數(shù)字三角形 456
訓(xùn)練3 最長(zhǎng)上升子序列 458
訓(xùn)練4 最長(zhǎng)公共子序列 461
訓(xùn)練5 最大連續(xù)子段和 462
7.4 區(qū)間DP 464
訓(xùn)練1 回文 464
訓(xùn)練2 括號(hào)匹配 466
訓(xùn)練3 猴子派對(duì) 468
訓(xùn)練4 乘法難題 470
7.5 樹(shù)形DP 472
訓(xùn)練1 別墅派對(duì) 473
訓(xùn)練2 戰(zhàn)略游戲 476
訓(xùn)練3 工人請(qǐng)?jiān)笗?shū) 478
訓(xùn)練4 完美的服務(wù) 480
訓(xùn)練5 背包類樹(shù)形DP 484
訓(xùn)練6 蘋(píng)果樹(shù) 487
訓(xùn)練7 二次掃描與換根 490
訓(xùn)練8 最遠(yuǎn)距離 494
7.6 數(shù)位DP 497
訓(xùn)練1 不吉利的數(shù)字 498
訓(xùn)練2 定時(shí)炸彈 503
訓(xùn)練3 Round Numbers 506
訓(xùn)練4 計(jì)數(shù)問(wèn)題 508
訓(xùn)練5 數(shù)字權(quán)值 511
7.7 狀態(tài)壓縮DP 513
訓(xùn)練1 旅行商問(wèn)題 514
訓(xùn)練2 旅行商變形1 520
訓(xùn)練3 旅行商變形2 521
訓(xùn)練4 玉米田 523
訓(xùn)練5 炮兵陣地 525
訓(xùn)練6 馬車旅行 528
7.8 插頭DP 531
訓(xùn)練1 鋪磚 531
訓(xùn)練2 方格取數(shù) 537
訓(xùn)練3 多回路連通性問(wèn)題 539
訓(xùn)練4 單回路連通性問(wèn)題 543
訓(xùn)練5 單通路連通性問(wèn)題 550
7.9 動(dòng)態(tài)規(guī)劃優(yōu)化 552
原理1 倍增優(yōu)化 552
原理2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化 552
訓(xùn)練1 最長(zhǎng)公共上升子序列 552
訓(xùn)練2 有序子序列 554
訓(xùn)練3 最大化器 557
訓(xùn)練4 灑水裝置 559
原理3 單調(diào)隊(duì)列優(yōu)化 562
訓(xùn)練5 滑動(dòng)窗口 563
訓(xùn)練6 灑水裝置 564
訓(xùn)練7 股票交易 565
原理4 斜率優(yōu)化 568
訓(xùn)練8 打印文章 569
訓(xùn)練9 覆蓋走道 573
訓(xùn)練10 批處理調(diào)度 575
訓(xùn)練11 劃分 580
訓(xùn)練12 勞倫斯 583
原理5 四邊不等式優(yōu)化 587
訓(xùn)練13 劃分 590

第8章 網(wǎng)絡(luò)流 592
8.1 EK算法 595
原理 EK算法詳解 595
訓(xùn)練1 最大流問(wèn)題 600
訓(xùn)練2 排水系統(tǒng) 600
8.2 Dinic算法 601
原理 Dinic算法詳解 601
訓(xùn)練1 最大銷售量 605
訓(xùn)練2 電力網(wǎng)絡(luò) 606
8.3 ISAP算法 608
原理 ISAP算法詳解 608
訓(xùn)練1 島嶼運(yùn)輸 613
訓(xùn)練2 美味佳肴 614
訓(xùn)練3 跳躍蜥蜴 615
訓(xùn)練4 計(jì)算機(jī)工廠 618
8.4 二分圖匹配 619
原理1 最大匹配算法 620
原理2 匈牙利算法 621
訓(xùn)練1 完美的牛棚 624
訓(xùn)練2 機(jī)器調(diào)度 625
訓(xùn)練3 逃脫 626
8.5 最大流最小割 627
原理 最大流最小割定理 627
訓(xùn)練1 最小邊割集 629
訓(xùn)練2 最小點(diǎn)割集 631
訓(xùn)練3 雙核CPU 632
訓(xùn)練4 最大收益 633
8.6 最小費(fèi)用最大流 635
原理 最小費(fèi)用路算法 635
訓(xùn)練1 農(nóng)場(chǎng)之旅 639
訓(xùn)練2 航空路線 640
訓(xùn)練3 區(qū)間覆蓋 642
訓(xùn)練4 疏散計(jì)劃 643