本書圖文并茂、通俗易懂，詳細(xì)講解常用的算法知識，又融入大量的競賽實例和解題技巧，可幫助讀者熟練應(yīng)用各種算法解決實際問題。本書總計8章。第1章講解STL，涉及雙端隊列、優(yōu)先隊列、位圖、集合、映射和STL中的常用函數(shù)；第2章講解實用的數(shù)據(jù)結(jié)構(gòu)，涉及并查集、倍增、稀疏表、區(qū)間最值查詢、最近公共祖先、樹狀數(shù)組和線段樹；第3章講解查找算法，涉及散列表、字符串模式匹配和字典樹；第4章講解平衡樹，涉及樹高與性能、平衡二叉搜索樹、樹堆和伸展樹；第5章講解圖論提高方面的知識，涉及連通圖與強(qiáng)連通圖、橋與割點(diǎn)、雙連通分量的縮點(diǎn)和Tarjan算法；第6章講解圖論算法，涉及最小生成樹、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑；第7章講解搜索算法提高方面的知識，涉及剪枝優(yōu)化、嵌套廣度優(yōu)先搜索、雙向廣度優(yōu)先搜索和啟發(fā)式搜索；第8章講解動態(tài)規(guī)劃提高方面的知識，涉及樹形動態(tài)規(guī)劃、狀態(tài)壓縮動態(tài)規(guī)劃和動態(tài)規(guī)劃優(yōu)化。本書面向?qū)λ惴ǜ信d趣的讀者，無論是想扎實內(nèi)功或參加算法競賽的學(xué)生，還是想進(jìn)入名企的學(xué)生、求職者，抑或是想提升核心競爭力的在職人員，都可以參考本書。若讀者想系統(tǒng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，則可參考《算法訓(xùn)練營：入門篇》（全彩版）和《算法訓(xùn)練營：進(jìn)階篇》（全彩版）。
陳小玉高級程序員，主要研究方向為算法優(yōu)化和機(jī)器學(xué)習(xí)。出版著作有《趣學(xué)算法》《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》《算法訓(xùn)練營》，所教學(xué)生多次獲得ACM-ICPC、藍(lán)橋杯等算法競賽獎項。
第1章 STL 1
1.1 deque（雙端隊列） 1
訓(xùn)練 度度熊學(xué)隊列 1
1.2 priority_queue（優(yōu)先隊列） 4
訓(xùn)練1 第k大的數(shù) 4
訓(xùn)練2 表演評分 6
1.3 bitset（位圖） 7
1.3.1 定義和初始化 8
1.3.2 基本操作 9
訓(xùn)練 集合運(yùn)算 10
1.4 set、multiset（集合、多重集合） 12
訓(xùn)練1 集合合并 13
訓(xùn)練2 并行處理 14
1.5 map、multimap（映射、多重映射） 16
訓(xùn)練1 硬木種類 18
訓(xùn)練2 水果 19
1.6 STL中的常用函數(shù) 21
1.6.1 fill() 21
1.6.2 nth_element() 22
1.6.3 lower_bound()、upper_bound() 23
1.6.4 next_permutation()、pre_permutation() 23
訓(xùn)練1 中位數(shù) 25
訓(xùn)練2 字謎 26
第2章 實用的數(shù)據(jù)結(jié)構(gòu) 28
2.1 并查集 28
訓(xùn)練1 暢通工程 33
訓(xùn)練2 方塊棧 35
2.2 倍增、稀疏表（ST）、區(qū)間最值查詢（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 區(qū)間最值查詢 41
訓(xùn)練1 區(qū)間最值差 41
訓(xùn)練2 最頻繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 樹上倍增法 47
2.3.3 在線區(qū)間最值查詢算法 51
2.3.4 離線Tarjan算法 53
訓(xùn)練1 最近公共祖先 57
訓(xùn)練2 樹上距離 59
2.4 樹狀數(shù)組 61
2.4.1 一維樹狀數(shù)組 61
2.4.2 多維樹狀數(shù)組 67
訓(xùn)練1 數(shù)星星 68
訓(xùn)練2 矩形區(qū)域查詢 70
2.5 線段樹 71
2.5.1 基本操作 71
2.5.2 懶操作 76
訓(xùn)練1 敵兵布陣 80
訓(xùn)練2 簡單的整數(shù)問題 83
第3章 查找算法 85
3.1 散列表 85
3.1.1 散列函數(shù) 86
3.1.2 開放地址法 88
3.1.3 鏈地址法 96
3.1.4 建立公共溢出區(qū) 98
3.1.5 散列查找及其性能分析 98
訓(xùn)練 雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
訓(xùn)練1 統(tǒng)計單詞數(shù) 109
訓(xùn)練2 字符串匹配 111
3.3 字典樹（Trie樹） 112
3.3.1 創(chuàng)建 113
3.3.2 查找 115
3.3.3 應(yīng)用 116
訓(xùn)練 單詞翻譯 116
第4章 平衡樹 118
4.1 樹高與性能 118
4.2 平衡二叉搜索樹（AVL樹） 119
4.2.1 調(diào)整平衡的方法 120
4.2.2 插入 122
4.2.3 創(chuàng)建 126
4.2.4 刪除 128
訓(xùn)練 雙重隊列 131
4.3 樹堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 刪除 138
4.3.4 前驅(qū) 140
4.3.5 后繼 140
訓(xùn)練 少林功夫 141
4.4 伸展樹（Splay樹） 144
4.4.1 時空局部性的原理 144
4.4.2 右旋和左旋 145
4.4.3 伸展 146
4.4.4 查找 149
4.4.5 插入 150
4.4.6 分裂 150
4.4.7 合并 150
4.4.8 刪除 151
4.4.9 區(qū)間操作 151
4.4.10 算法分析 152
訓(xùn)練1 玩鏈子 152
訓(xùn)練2 超強(qiáng)記憶 159
第5章 圖論提高 169
5.1 連通圖與強(qiáng)連通圖 169
5.2 橋與割點(diǎn) 170
5.3 雙連通分量的縮點(diǎn) 171
5.4 Tarjan算法 172
5.4.1 無向圖的橋 173
5.4.2 無向圖的割點(diǎn) 174
5.4.3 有向圖的強(qiáng)連通分量 175
訓(xùn)練1 道路建設(shè) 177
訓(xùn)練2 校園網(wǎng)絡(luò) 180
第6章 圖論算法 183
6.1 最小生成樹 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
訓(xùn)練1 叢林之路 195
訓(xùn)練2 聯(lián)網(wǎng) 197
6.2 最短路徑 199
6.2.1 Dijkstra算法 199
6.2.2 Floyd算法 204
6.2.3 Bellman-Ford算法 208
6.2.4 SPFA算法 209
訓(xùn)練1 重型運(yùn)輸 211
訓(xùn)練2 貨幣兌換 212
訓(xùn)練3 蟲洞 214
6.3 拓?fù)渑判? 216
訓(xùn)練1 家族樹 220
訓(xùn)練2 標(biāo)簽球 222
6.4 關(guān)鍵路徑 224
訓(xùn)練1 指令安排 232
訓(xùn)練2 家務(wù)瑣事 233
第7章 搜索算法提高 235
7.1 剪枝優(yōu)化 235
訓(xùn)練1 數(shù)獨(dú)游戲 235
訓(xùn)練2 小木棍 238
7.2 嵌套廣度優(yōu)先搜索 240
訓(xùn)練 推箱子 240
7.3 雙向廣度優(yōu)先搜索 244
訓(xùn)練 魔鬼Ⅱ 244
7.4 啟發(fā)式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
訓(xùn)練1 八數(shù)碼問題 248
訓(xùn)練2 第k短路徑 257
第8章 動態(tài)規(guī)劃提高 260
8.1 樹形動態(tài)規(guī)劃 260
訓(xùn)練1 戰(zhàn)略游戲 260
訓(xùn)練2 工人請愿書 262
8.2 狀態(tài)壓縮動態(tài)規(guī)劃 264
訓(xùn)練1 旅行商問題 265
訓(xùn)練2 玉米田 269
8.3 動態(tài)規(guī)劃優(yōu)化 271
8.3.1 倍增優(yōu)化 272
8.3.2 數(shù)據(jù)結(jié)構(gòu)優(yōu)化 272
8.3.3 單調(diào)隊列優(yōu)化 272
訓(xùn)練1 最長公共上升子序列 273
訓(xùn)練2 滑動窗口 275
書單推薦
