本书图文并茂、通俗易懂，详细讲解常用的算法知识，又融入大量的竞赛实例和解题技巧，可帮助读者熟练应用各种算法解决实际问题。本书总计8章。第1章讲解STL，涉及双端队列、优先队列、位图、集合、映射和STL中的常用函数；第2章讲解实用的数据结构，涉及并查集、倍增、稀疏表、区间最值查询、最近公共祖先、树状数组和线段树；第3章讲解查找算法，涉及散列表、字符串模式匹配和字典树；第4章讲解平衡树，涉及树高与性能、平衡二叉搜索树、树堆和伸展树；第5章讲解图论提高方面的知识，涉及连通图与强连通图、桥与割点、双连通分量的缩点和Tarjan算法；第6章讲解图论算法，涉及最小生成树、最短路径、拓扑排序和关键路径；第7章讲解搜索算法提高方面的知识，涉及剪枝优化、嵌套广度优先搜索、双向广度优先搜索和启发式搜索；第8章讲解动态规划提高方面的知识，涉及树形动态规划、状态压缩动态规划和动态规划优化。本书面向对算法感兴趣的读者，无论是想扎实内功或参加算法竞赛的学生，还是想进入名企的学生、求职者，抑或是想提升核心竞争力的在职人员，都可以参考本书。若读者想系统学习数据结构与算法，则可参考《算法训练营：入门篇》（全彩版）和《算法训练营：进阶篇》（全彩版）。

陈小玉高级程序员，主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营》，所教学生多次获得ACM-ICPC、蓝桥杯等算法竞赛奖项。

第1章 STL 1
1.1 deque（双端队列） 1
训练 度度熊学队列 1
1.2 priority_queue（优先队列） 4
训练1 第k大的数 4
训练2 表演评分 6
1.3 bitset（位图） 7
1.3.1 定义和初始化 8
1.3.2 基本操作 9
训练 集合运算 10
1.4 set、multiset（集合、多重集合） 12
训练1 集合合并 13
训练2 并行处理 14
1.5 map、multimap（映射、多重映射） 16
训练1 硬木种类 18
训练2 水果 19
1.6 STL中的常用函数 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
训练1 中位数 25
训练2 字谜 26

第2章 实用的数据结构 28
2.1 并查集 28
训练1 畅通工程 33
训练2 方块栈 35
2.2 倍增、稀疏表（ST）、区间最值查询（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 区间最值查询 41
训练1 区间最值差 41
训练2 最频繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 树上倍增法 47
2.3.3 在线区间最值查询算法 51
2.3.4 离线Tarjan算法 53
训练1 最近公共祖先 57
训练2 树上距离 59
2.4 树状数组 61
2.4.1 一维树状数组 61
2.4.2 多维树状数组 67
训练1 数星星 68
训练2 矩形区域查询 70
2.5 线段树 71
2.5.1 基本操作 71
2.5.2 懒操作 76
训练1 敌兵布阵 80
训练2 简单的整数问题 83

第3章 查找算法 85
3.1 散列表 85
3.1.1 散列函数 86
3.1.2 开放地址法 88
3.1.3 链地址法 96
3.1.4 建立公共溢出区 98
3.1.5 散列查找及其性能分析 98
训练 雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
训练1 统计单词数 109
训练2 字符串匹配 111
3.3 字典树（Trie树） 112
3.3.1 创建 113
3.3.2 查找 115
3.3.3 应用 116
训练 单词翻译 116

第4章 平衡树 118
4.1 树高与性能 118
4.2 平衡二叉搜索树（AVL树） 119
4.2.1 调整平衡的方法 120
4.2.2 插入 122
4.2.3 创建 126
4.2.4 删除 128
训练 双重队列 131
4.3 树堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 删除 138
4.3.4 前驱 140
4.3.5 后继 140
训练 少林功夫 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 区间操作 151
4.4.10 算法分析 152
训练1 玩链子 152
训练2 超强记忆 159

第5章 图论提高 169
5.1 连通图与强连通图 169
5.2 桥与割点 170
5.3 双连通分量的缩点 171
5.4 Tarjan算法 172
5.4.1 无向图的桥 173
5.4.2 无向图的割点 174
5.4.3 有向图的强连通分量 175
训练1 道路建设 177
训练2 校园网络 180

第6章 图论算法 183
6.1 最小生成树 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
训练1 丛林之路 195
训练2 联网 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
训练1 重型运输 211
训练2 货币兑换 212
训练3 虫洞 214
6.3 拓扑排序 216
训练1 家族树 220
训练2 标签球 222
6.4 关键路径 224
训练1 指令安排 232
训练2 家务琐事 233

第7章 搜索算法提高 235
7.1 剪枝优化 235
训练1 数独游戏 235
训练2 小木棍 238
7.2 嵌套广度优先搜索 240
训练 推箱子 240
7.3 双向广度优先搜索 244
训练 魔鬼Ⅱ 244
7.4 启发式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
训练1 八数码问题 248
训练2 第k短路径 257

第8章 动态规划提高 260
8.1 树形动态规划 260
训练1 战略游戏 260
训练2 工人请愿书 262
8.2 状态压缩动态规划 264
训练1 旅行商问题 265
训练2 玉米田 269
8.3 动态规划优化 271
8.3.1 倍增优化 272
8.3.2 数据结构优化 272
8.3.3 单调队列优化 272
训练1 最长公共上升子序列 273
训练2 滑动窗口 275