算法训练营：进阶篇（全彩版）

第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