第1章 實用數(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)先隊列 19
原理1 優(yōu)先隊列的實現(xiàn)原理 19
原理2 優(yōu)先隊列詳解 23
訓(xùn)練1 第k大的數(shù) 26
訓(xùn)練2 圍欄修復(fù) 27
訓(xùn)練3 表演評分 29
訓(xùn)練4 叢林探險 30

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

第3章 字符串處理 115
3.1 字典樹 115
原理 字典樹詳解 115
訓(xùn)練1 單詞翻譯 120
訓(xùn)練2 電話表 122
訓(xùn)練3 統(tǒng)計難題 123
訓(xùn)練4 彩色的木棒 124
訓(xùn)練5 最長xor路徑 127
3.2 AC自動機 129
原理 AC自動機詳解 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 音樂主題 173
訓(xùn)練4 星際迷航 175

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

第5章 平衡二叉樹 263
5.1 Treap 263
原理 Treap詳解 263
訓(xùn)練1 雙重隊列 270
訓(xùn)練2 普通平衡樹 272
訓(xùn)練3 黑盒子 276
訓(xùn)練4 少林功夫 279
5.2 伸展樹 283
原理 伸展樹詳解 283
訓(xùn)練1 雙重隊列 291
訓(xùn)練2 玩鏈子 293
訓(xùn)練3 超強記憶 300
訓(xùn)練4 循環(huán) 310
5.3 SBT 324
原理 SBT詳解 324
訓(xùn)練1 雙重隊列 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)進階 339
6.1 KD樹 339
原理 KD樹詳解 339
訓(xùn)練1 最近的取款機 343
訓(xùn)練2 找旅館 346
訓(xùn)練3 最近鄰M點 348
訓(xùn)練4 蟻巢 349
6.2 左偏樹 352
原理 左偏樹詳解 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 雙重隊列 379
訓(xùn)練2 第k大的數(shù) 381
訓(xùn)練3 郁悶的出納員 386
6.4 樹套樹 388
原理 樹套樹詳解 388
訓(xùn)練1 動態(tài)區(qū)間問題 389
訓(xùn)練2 動態(tài)區(qū)間第k小 395
訓(xùn)練3 矩形區(qū)域查詢 396
訓(xùn)練4 馬賽克處理 400
6.5 可持久化數(shù)據(jù)結(jié)構(gòu) 406
原理1 可持久化線段樹詳解 406
原理2 可持久化Trie詳解 413
訓(xùn)練1 超級馬里奧 415
訓(xùn)練2 記憶重現(xiàn) 419
訓(xùn)練3 最大異或和 424

第7章 動態(tài)規(guī)劃及其優(yōu)化 431
7.1 動態(tài)規(guī)劃求解原理 431
原理1 動態(tài)規(guī)劃的三個要素 432
原理2 動態(tài)規(guī)劃設(shè)計方法 432
7.2 背包問題 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 價值最大化 450
原理5 混合背包 452
訓(xùn)練5 最少的硬幣 452
7.3 線性DP 455
訓(xùn)練1 超級樓梯 455
訓(xùn)練2 數(shù)字三角形 456
訓(xùn)練3 最長上升子序列 458
訓(xùn)練4 最長公共子序列 461
訓(xùn)練5 最大連續(xù)子段和 462
7.4 區(qū)間DP 464
訓(xùn)練1 回文 464
訓(xùn)練2 括號匹配 466
訓(xùn)練3 猴子派對 468
訓(xùn)練4 乘法難題 470
7.5 樹形DP 472
訓(xùn)練1 別墅派對 473
訓(xùn)練2 戰(zhàn)略游戲 476
訓(xùn)練3 工人請愿書 478
訓(xùn)練4 完美的服務(wù) 480
訓(xùn)練5 背包類樹形DP 484
訓(xùn)練6 蘋果樹 487
訓(xùn)練7 二次掃描與換根 490
訓(xùn)練8 最遠距離 494
7.6 數(shù)位DP 497
訓(xùn)練1 不吉利的數(shù)字 498
訓(xùn)練2 定時炸彈 503
訓(xùn)練3 Round Numbers 506
訓(xùn)練4 計數(shù)問題 508
訓(xùn)練5 數(shù)字權(quán)值 511
7.7 狀態(tài)壓縮DP 513
訓(xùn)練1 旅行商問題 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 多回路連通性問題 539
訓(xùn)練4 單回路連通性問題 543
訓(xùn)練5 單通路連通性問題 550
7.9 動態(tài)規(guī)劃優(yōu)化 552
原理1 倍增優(yōu)化 552
原理2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化 552
訓(xùn)練1 最長公共上升子序列 552
訓(xùn)練2 有序子序列 554
訓(xùn)練3 最大化器 557
訓(xùn)練4 灑水裝置 559
原理3 單調(diào)隊列優(yōu)化 562
訓(xùn)練5 滑動窗口 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 最大流問題 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 島嶼運輸 613
訓(xùn)練2 美味佳肴 614
訓(xùn)練3 跳躍蜥蜴 615
訓(xùn)練4 計算機工廠 618
8.4 二分圖匹配 619
原理1 最大匹配算法 620
原理2 匈牙利算法 621
訓(xùn)練1 完美的牛棚 624
訓(xùn)練2 機器調(diào)度 625
訓(xùn)練3 逃脫 626
8.5 最大流最小割 627
原理 最大流最小割定理 627
訓(xùn)練1 最小邊割集 629
訓(xùn)練2 最小點割集 631
訓(xùn)練3 雙核CPU 632
訓(xùn)練4 最大收益 633
8.6 最小費用最大流 635
原理 最小費用路算法 635
訓(xùn)練1 農(nóng)場之旅 639
訓(xùn)練2 航空路線 640
訓(xùn)練3 區(qū)間覆蓋 642
訓(xùn)練4 疏散計劃 643