数据结构解题策略

本书以面对纷呈复杂问题时如何理清数据关系，选择适宜高效的数据结构和解题方法为主线，分别阐述线性表、树、图的解题策略，全书共16章。每章以相关的数据结构、高级数据结构的知识体系为大纲，以基于程序设计竞赛试题的解题实验为核心单元，以期通过案例化的学习，系统、全面地提高读者编程解决问题的能力。本书既可以作为ACM-ICPC、IOI等各类程序设计竞赛的训练教程，又可以作为大学本科、研究生的教材，也可以作为IT研发人员提高编程能力的辅导教材。

本书以面对纷呈复杂问题时如何理清数据关系，选择适宜高效的数据结构和解题方法为主线，分别阐述线性表、树、图的解题策略，全书共16章。每章以相关的数据结构、高级数据结构的知识体系为大纲，以基于程序设计竞赛试题的解题实验为核心单元，以期通过案例化的学习，系统、全面地提高读者编程解决问题的能力。本书既可以作为ACM-ICPC、IOI等各类程序设计竞赛的训练教程，又可以作为大学本科、研究生的教材，也可以作为IT研发人员提高编程能力的辅导教材。

前言
第一篇线性表的解题策略
第1章利用快速幂提高幂运算效率2
1.1快速幂取模2
1.1.1快速幂取模的概念2
1.1.2快速幂取模的应用4
1.2矩阵快速幂10
1.2.1矩阵快速幂的概念10
1.2.2矩阵快速幂的应用14
第2章高斯消元法22
2.1高斯消元法求解线性方程组22
2.2高斯消元法求解模线性方程组30
2.3高斯消元法求解异或方程组38
2.4高斯消元求矩阵的秩49
第3章单调栈和单调队列52
3.1单调栈52
3.2二维空间中应用单调栈61
3.3单调队列65
3.4单调队列优化DP69
3.5单调队列优化DP之多重背包问题78
第一篇小结83
第二篇树的解题策略
第4章利用划分树查找有序数86
4.1离线构建整个查询区间的划分树87
4.2在划分树上查找子区间[l,r]中按序排列的第k个值88
4.3利用划分树解题88
第5章利用线段树解决区间计算问题97
5.1线段树的基本概念和基本操作97
5.2线段树动态维护：单点更新101
5.3线段树动态维护：子区间更新和懒惰标记106
5.4线段树动态维护：子区间合并112
5.5权值线段树120
5.6主席树125
第6章最小生成树的拓展129
6.1最小生成树的应用129
6.2很优比率生成树143
6.3最小k度生成树148
6.4次小生成树154
第7章利用改进型的二叉搜索树优化动态集合的操作171
7.1伸展树171
7.2红黑树198
第8章利用左偏树实现优先队列的合并212
8.1左偏树的基本概念212
8.2利用左偏树解题216
第9章利用动态树维护森林的连通性230
9.1树链剖分230
9.2动态树241
第10章利用跳跃表替代树结构260
10.1跳跃表的基本概念260
10.2利用跳跃表解题265
第二篇小结279
第三篇图的解题策略
第11章网络流算法282
11.1利用Dinic算法求解优选流282
11.2求容量有上下界的网络流问题298
11.2.1求解无源汇且容量有上下界的网络可行流问题298
11.2.2求解有源汇且容量有上下界的网络优选流问题307
11.2.3求解有源汇且容量有上下界的网络最小流问题316
11.3计算最小（优选）费用优选流321
第12章二分图匹配329
12.1匈牙利算法329
12.2稳定婚姻问题344
12.3KM算法350
12.4利用一一对应的匹配性质转化问题的实验范例358
第13章平面图、图的着色与偏序关系371
13.1平面图371
13.2图的着色380
13.3黑白着色法判定二分图383
13.4偏序关系395
第14章分层图407
14.1体验“分层图”思想内涵407
14.2基于动态规划利用“分层图”求解最短路径问题417
14.3利用“分层图”思想优化算法425
第15章可简单图化与图的计数430
15.1可简单图化430
15.2生成树计数435
15.3基于遍历的图的计数446
15.4基于组合分析的图的计数451
第16章挖掘和利用图的性质460
16.1挖掘和利用图的性质的方法460
16.2挖掘和利用图的性质的实验范例460
第三篇小结468