本書以海量圖解的形式，詳細講解常用的數(shù)據(jù)結構與算法，并結合競賽實例引導讀者進行刷題實戰(zhàn)。通過對本書的學習，讀者將掌握22種高級數(shù)據(jù)結構、7種動態(tài)規(guī)劃算法、5種動態(tài)規(guī)劃優(yōu)化技巧，以及5種網(wǎng)絡流算法，并熟練應用各種算法解決實際問題。 本書總計8章。第1章講解實用數(shù)據(jù)結構，包括并查集、優(yōu)先隊列；第2章講解區(qū)間信息維護與查詢，包括倍增、ST、RMQ、LCA、樹狀數(shù)組、線段樹和分塊；第3章講解字符串處理，包括字典樹、AC自動機和后綴數(shù)組；第4章講解樹上操作問題，包括點分治、邊分治、樹鏈剖分和動態(tài)樹；第5章講解各種平衡二叉樹，包括Treap、伸展樹和SBT；第6章講解數(shù)據(jù)結構進階，包括KD樹、左偏樹、跳躍表、樹套樹和可持久化數(shù)據(jù)結構；第7章講解動態(tài)規(guī)劃及其優(yōu)化，包括背包問題、線性DP、區(qū)間DP、樹形DP、數(shù)位DP、狀態(tài)壓縮DP、插頭DP和動態(tài)規(guī)劃優(yōu)化方法；第8章講解網(wǎng)絡流問題，包括常用網(wǎng)絡流算法、二分圖最大匹配、最大流最小割定理和最小費用最大流。本書對每個算法都進行詳細圖解并搭配競賽實例，重點講解如何分析問題、優(yōu)化算法，以期讀者在短時間內(nèi)掌握該算法并進行刷題實戰(zhàn)。
陳小玉 南陽理工學院副教授，高級程序員，主要研究方向為算法優(yōu)化和機器學習。出版著作有《趣學算法》《趣學數(shù)據(jù)結構》《算法訓練營：海量圖解+競賽刷題（入門篇）》《算法訓練營：海量圖解+競賽刷題（進階篇）》，所教學生多次獲得ACM、藍橋杯等算法競賽獎項。推薦語
第1章 實用數(shù)據(jù)結構 1
1.1 并查集 1
原理 并查集詳解 1
訓練1 暢通工程 6
訓練2 方塊棧 7
訓練3 食物鏈 10
訓練4 幫派 16
1.2 優(yōu)先隊列 19
原理1 優(yōu)先隊列的實現(xiàn)原理 19
原理2 優(yōu)先隊列詳解 23
訓練1 第k大的數(shù) 26
訓練2 圍欄修復 27
訓練3 表演評分 29
訓練4 叢林探險 30
第2章 區(qū)間信息維護與查詢 33
2.1 倍增、ST、RMQ 33
原理1 倍增 33
原理2 ST 34
原理3 RMQ 36
訓練1 區(qū)間最值差 36
訓練2 最頻繁值 37
訓練3 最小分段數(shù) 40
訓練4 二維區(qū)間最值差 41
2.2 最近公共祖先LCA 43
原理1 暴力搜索法 44
原理2 樹上倍增法 45
原理3 在線RMQ算法 49
原理4 Tarjan算法 51
訓練1 最近公共祖先 55
訓練2 樹上距離 57
訓練3 距離查詢 59
訓練4 城市之間的聯(lián)系 60
2.3 樹狀數(shù)組 62
原理1 一維樹狀數(shù)組 62
原理2 多維樹狀數(shù)組 67
訓練1 數(shù)星星 69
訓練2 公路交叉數(shù) 71
訓練3 子樹查詢 74
訓練4 矩形區(qū)域查詢 76
2.4 線段樹 78
原理1 線段樹的基本操作 78
原理2 線段樹中的“懶操作” 83
訓練1 敵兵布陣 87
訓練2 簡單的整數(shù)問題 89
訓練3 數(shù)據(jù)結構難題 91
訓練4 顏色統(tǒng)計 97
2.5 分塊 102
原理 分塊詳解 102
訓練1 簡單的整數(shù)問題 105
訓練2 數(shù)字序列 106
訓練3 區(qū)間最值差 107
訓練4 超級馬里奧 109
訓練5 序列操作 111
第3章 字符串處理 115
3.1 字典樹 115
原理 字典樹詳解 115
訓練1 單詞翻譯 120
訓練2 電話表 122
訓練3 統(tǒng)計難題 123
訓練4 彩色的木棒 124
訓練5 最長xor路徑 127
3.2 AC自動機 129
原理 AC自動機詳解 129
訓練1 關鍵字檢索 132
訓練2 病毒侵襲 134
訓練3 DNA序列 136
訓練4 單詞情結 140
3.3 后綴數(shù)組 145
原理1 基數(shù)排序 145
原理2 后綴數(shù)組詳解 152
訓練1 牛奶模式 169
訓練2 口吃的外星人 171
訓練3 音樂主題 173
訓練4 星際迷航 175
第4章 樹上操作 178
4.1 點分治 178
原理 重心分解 178
訓練1 樹上兩點之間的路徑數(shù) 179
訓練2 游船之旅 185
訓練3 摩天大樹 189
訓練4 查詢子樹 194
4.2 邊分治 200
原理 邊分治詳解 200
訓練1 樹上查詢I 203
訓練2 樹上查詢II 212
訓練3 樹上兩點之間的路徑數(shù) 217
4.3 樹鏈剖分 221
原理 樹鏈剖分詳解 221
訓練1 樹上距離 230
訓練2 樹的統(tǒng)計 231
訓練3 家庭主婦 232
訓練4 樹上操作 233
4.4 動態(tài)樹 236
原理 動態(tài)樹詳解 236
訓練1 距離查詢 247
訓練2 動態(tài)樹xor和 249
訓練3 動態(tài)樹的最值 252
訓練4 動態(tài)樹的第2大值 255
訓練5 樹上操作 261
第5章 平衡二叉樹 263
5.1 Treap 263
原理 Treap詳解 263
訓練1 雙重隊列 270
訓練2 普通平衡樹 272
訓練3 黑盒子 276
訓練4 少林功夫 279
5.2 伸展樹 283
原理 伸展樹詳解 283
訓練1 雙重隊列 291
訓練2 玩鏈子 293
訓練3 超強記憶 300
訓練4 循環(huán) 310
5.3 SBT 324
原理 SBT詳解 324
訓練1 雙重隊列 331
訓練2 第k小的數(shù) 333
訓練3 第k大的數(shù) 334
訓練4 區(qū)間第k小 334
訓練5 郁悶的出納員 336
第6章 數(shù)據(jù)結構進階 339
6.1 KD樹 339
原理 KD樹詳解 339
訓練1 最近的取款機 343
訓練2 找旅館 346
訓練3 最近鄰M點 348
訓練4 蟻巢 349
6.2 左偏樹 352
原理 左偏樹詳解 352
訓練1 猴王 360
訓練2 小根堆 363
訓練3 路面修整 365
訓練4 K-單調(diào) 369
6.3 跳躍表 373
原理 跳躍表詳解 373
訓練1 雙重隊列 379
訓練2 第k大的數(shù) 381
訓練3 郁悶的出納員 386
6.4 樹套樹 388
原理 樹套樹詳解 388
訓練1 動態(tài)區(qū)間問題 389
訓練2 動態(tài)區(qū)間第k小 395
訓練3 矩形區(qū)域查詢 396
訓練4 馬賽克處理 400
6.5 可持久化數(shù)據(jù)結構 406
原理1 可持久化線段樹詳解 406
原理2 可持久化Trie詳解 413
訓練1 超級馬里奧 415
訓練2 記憶重現(xiàn) 419
訓練3 最大異或和 424
第7章 動態(tài)規(guī)劃及其優(yōu)化 431
7.1 動態(tài)規(guī)劃求解原理 431
原理1 動態(tài)規(guī)劃的三個要素 432
原理2 動態(tài)規(guī)劃設計方法 432
7.2 背包問題 433
原理1 01背包 433
訓練1 骨頭收藏家 441
原理2 完全背包 443
訓練2 存錢罐 443
原理3 多重背包 445
訓練3 硬幣 447
原理4 分組背包 449
訓練4 價值最大化 450
原理5 混合背包 452
訓練5 最少的硬幣 452
7.3 線性DP 455
訓練1 超級樓梯 455
訓練2 數(shù)字三角形 456
訓練3 最長上升子序列 458
訓練4 最長公共子序列 461
訓練5 最大連續(xù)子段和 462
7.4 區(qū)間DP 464
訓練1 回文 464
訓練2 括號匹配 466
訓練3 猴子派對 468
訓練4 乘法難題 470
7.5 樹形DP 472
訓練1 別墅派對 473
訓練2 戰(zhàn)略游戲 476
訓練3 工人請愿書 478
訓練4 完美的服務 480
訓練5 背包類樹形DP 484
訓練6 蘋果樹 487
訓練7 二次掃描與換根 490
訓練8 最遠距離 494
7.6 數(shù)位DP 497
訓練1 不吉利的數(shù)字 498
訓練2 定時炸彈 503
訓練3 Round Numbers 506
訓練4 計數(shù)問題 508
訓練5 數(shù)字權值 511
7.7 狀態(tài)壓縮DP 513
訓練1 旅行商問題 514
訓練2 旅行商變形1 520
訓練3 旅行商變形2 521
訓練4 玉米田 523
訓練5 炮兵陣地 525
訓練6 馬車旅行 528
7.8 插頭DP 531
訓練1 鋪磚 531
訓練2 方格取數(shù) 537
訓練3 多回路連通性問題 539
訓練4 單回路連通性問題 543
訓練5 單通路連通性問題 550
7.9 動態(tài)規(guī)劃優(yōu)化 552
原理1 倍增優(yōu)化 552
原理2 數(shù)據(jù)結構優(yōu)化 552
訓練1 最長公共上升子序列 552
訓練2 有序子序列 554
訓練3 最大化器 557
訓練4 灑水裝置 559
原理3 單調(diào)隊列優(yōu)化 562
訓練5 滑動窗口 563
訓練6 灑水裝置 564
訓練7 股票交易 565
原理4 斜率優(yōu)化 568
訓練8 打印文章 569
訓練9 覆蓋走道 573
訓練10 批處理調(diào)度 575
訓練11 劃分 580
訓練12 勞倫斯 583
原理5 四邊不等式優(yōu)化 587
訓練13 劃分 590
第8章 網(wǎng)絡流 592
8.1 EK算法 595
原理 EK算法詳解 595
訓練1 最大流問題 600
訓練2 排水系統(tǒng) 600
8.2 Dinic算法 601
原理 Dinic算法詳解 601
訓練1 最大銷售量 605
訓練2 電力網(wǎng)絡 606
8.3 ISAP算法 608
原理 ISAP算法詳解 608
訓練1 島嶼運輸 613
訓練2 美味佳肴 614
訓練3 跳躍蜥蜴 615
訓練4 計算機工廠 618
8.4 二分圖匹配 619
原理1 最大匹配算法 620
原理2 匈牙利算法 621
訓練1 完美的牛棚 624
訓練2 機器調(diào)度 625
訓練3 逃脫 626
8.5 最大流最小割 627
原理 最大流最小割定理 627
訓練1 最小邊割集 629
訓練2 最小點割集 631
訓練3 雙核CPU 632
訓練4 最大收益 633
8.6 最小費用最大流 635
原理 最小費用路算法 635
訓練1 農(nóng)場之旅 639
訓練2 航空路線 640
訓練3 區(qū)間覆蓋 642
訓練4 疏散計劃 643
書單推薦
