本书图文并茂、通俗易懂，详细讲解数据结构和算法进阶知识，并融入大量的竞赛实例和解题技巧，可帮助读者领悟数据结构和算法的精髓，并熟练应用其解决实际问题。 本书总计8章。第1章讲解数据结构进阶知识，涉及分块算法和跳跃表；第2章讲解字符串算法进阶知识，涉及AC自动机和后缀数组；第3章讲解树上操作，涉及树链剖分、点分治和边分治；第4章讲解复杂树，涉及KD树、左偏树、动态树和树套树；第5章讲解可持久化数据结构，涉及可持久化线段树和可持久化字典树；第6章讲解图论算法进阶知识，涉及EK算法、Dinic算法、ISAP算法、二分图匹配、最大流最小割和最小费用最大流；第7章讲解动态规划进阶知识，涉及背包问题进阶知识和树形DP进阶知识；第8章讲解复杂动态规划及其优化，涉及数位DP、插头DP、斜率优化和四边不等式优化。
陈小玉高级程序员，主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营》，所教学生多次获得ACM-ICPC、蓝桥杯等算法竞赛奖项。
第1章 数据结构进阶 1
1.1 分块算法 1
1.1.1 预处理 2
1.1.2 区间更新 2
1.1.3 区间查询 3
训练1 超级马里奥 4
训练2 序列操作 7
1.2 跳跃表 9
1.2.1 跳跃表的结构体定义 11
1.2.2 查找 12
1.2.3 插入 13
1.2.4 删除 14
训练1 第k大的数 15
训练2 郁闷的出纳员 21
第2章 字符串算法进阶 24
2.1 AC自动机 24
2.1.1 创建字典树 24
2.1.2 创建AC自动机 25
2.1.3 模式匹配 27
训练1 病毒侵袭 28
训练2 DNA序列 30
2.2 后缀数组 34
2.2.1 基数排序 34
2.2.2 后缀数组详解 41
2.2.3 后缀数组的应用 50
训练1 牛奶模式 57
训练2 音乐主题 60
第3章 树上操作 62
3.1 树链剖分 62
3.1.1 预处理 63
3.1.2 求解最近公共祖先 63
3.1.3 树链剖分与线段树 66
训练1 树上距离 71
训练2 树上操作 73
3.2 点分治 76
3.2.1 树的重心 76
3.2.2 重心分解 77
训练1 树上两个节点之间的路径数 77
训练2 游船之旅 83
3.3 边分治 88
3.3.1 重建树 88
3.3.2 求解中心边 89
3.3.3 中心边分解 90
训练1 树上查询 91
训练2 树上两个节点之间的路径数 100
第4章 复杂树 104
4.1 KD树 104
4.1.1 创建KD树 104
4.1.2 搜索m近邻 106
训练1 最近的取款机 107
训练2 最近邻m点 110
4.2 左偏树 112
4.2.1 左偏树的性质 112
4.2.2 基本操作 114
训练1 猴王 120
训练2 小根堆 123
4.3 动态树 125
4.3.1 LCT的性质 126
4.3.2 LCT的基本操作 127
训练1 动态树的异或和 136
训练2 动态树的最值 139
4.4 树套树 142
4.4.1 线段树套平衡树 142
4.4.2 线段树套线段树 143
训练1 动态区间问题 143
训练2 打马赛克 149
第5章 可持久化数据结构 156
5.1 可持久化线段树 156
训练1 超级马里奥 163
训练2 记忆重现 167
5.2 可持久化字典树 172
训练 最大异或和 173
第6章 图论算法进阶 180
6.1 EK算法 183
训练 排水系统 188
6.2 Dinic算法 188
训练 电力网络 193
6.3 ISAP算法 195
训练 美味佳肴 200
6.4 二分图匹配 201
6.4.1 最大匹配算法 202
6.4.2 匈牙利算法 202
训练1 完美的牛棚 206
训练2 逃脱 207
6.5 最大流最小割 208
训练1 最小边割集 210
训练2 最小点割集 211
训练3 最大收益 213
6.6 最小费用最大流 214
训练1 农场之旅 218
训练2 航空路线 219
第7章 动态规划进阶 222
7.1 背包问题进阶 222
7.1.1 多重背包问题 222
训练 硬币 224
7.1.2 分组背包问题 227
训练 价值最大化 228
7.1.3 混合背包问题 229
训练 最少硬币 230
7.2 树形DP进阶 232
7.2.1 背包类树形DP 232
训练1 城堡中的宝物 232
训练2 苹果树 235
7.2.2 不定根树形DP 238
训练1 最大累积度 239
训练2 最远距离 243
第8章 复杂动态规划及其
优化 247
8.1 数位DP 247
训练1 不吉利的数字 247
训练2 定时炸弹 253
8.2 插头DP 255
训练1 铺砖 256
训练2 多回路连通性问题 262
8.3 斜率优化 266
训练1 打印文章 266
训练2 批处理作业 270
8.4 四边不等式优化 275
训练 划分 277
书单推荐
