高级数据结构

本书在基本数据结构的基础上，围绕一些常用的不错数据结构，结合大量实战例题，深入分析“数据结构是如何服务于算法的”，这也是本书编写的一个核心理念：学习数据结构是为了“用好”数据结构。本次修订除了改错，主要是更换全书的程序代码为（C++）。本书的适用对象包括：中学信息学竞赛选手及辅导老师、大学ACM比赛选手及教练、高等院校计算机专业的师生、程序设计爱好者等。

第1章哈希表
1.1哈希表的基本原理
1.2哈希表的基本概念
1.3哈希函数的构造
1.4哈希表的基本操作
1.5冲突的处理
1.6哈希表的性能分析
1.7哈希表的应用举例
1.8本章习题
第2章树与二叉树
2.1树
2.1.1树的存储结构
2.1.2树的遍历
2.2二叉树
2.2.1普通树转换成二叉树
2.2.2二叉树的遍历
2.2.3二叉树的其他操作
2.2.4二叉树的形态
2.3二叉排序树
2.4哈夫曼二叉树
2.5字典树
2.6本章习题
第3章优先队列与二叉堆
3.1优先队列
3.2二叉堆
3.2.1Put操作
3.2.2Get操作
3.3可并堆
3.3.1左偏树的定义
3.3.2左偏树的基本操作
3.4本章习题
第4章并查集
4.1并查集的主要操作
4.2并查集的实现
4.2.1并查集的数组实现
4.2.2并查集的链表实现
4.2.3并查集的树实现
4.3并查集的应用举例
4.4本章习题
第5章线段树
5.1线段树的应用背景
5.2线段树的初步实现
5.2.1线段树的结构
5.2.2线段树的性质
5.2.3线段树的存储
5.2.4线段树的常用操作
5.2.4.1线段树的构造
5.2.4.2线段树的查询
5.2.4.3线段树的修改
5.2.4.4线段树的延迟修改
5.3线段树在一些经典问题中的应用
5.3.1逆序对问题
5.3.2矩形覆盖问题
5.4线段树的扩展
5.4.1用线段树优化动态规划
5.4.2将线段树扩展到高维
5.4.3线段树与平衡树的结合
5.5线段树与其他数据结构的比较
5.6线段树的应用举例
5.7本章习题
第6章树状数组
6.1树状数组的问题模型
6.2树状数组的基本思想
6.3树状数组的实现
6.3.1子集的划分方法
6.3.2查询前缀和
6.3.3修改子集和
6.4树状数组的常用技巧
6.4.1查询任意区间和
6.4.2利用sum数组求出原数组a的某个元素值
6.4.3找到某个前缀和对应的前缀下标index
6.4.4成倍扩张／缩减
6.4.5初始化树状数组
6.5树状数组与线段树的比较
6.6树状数组扩展到高维的情形
6.7树状数组的应用举例
6.8本章习题
第7章伸展树
7.1伸展树的主要操作
7.1.1伸展操作
7.1.2伸展树的基本操作
7.2伸展树的算法实现
7.3伸展树的效率分析
7.4伸展树的应用举例
7.5本章习题
第8章Treap
8.1Treap的基本操作
8.2Treap的算法实现
8.3Treap的应用举例
8.4本章习题
第9章平衡树
9.1AVL树
9.2红一黑树
9.3SBT
9.3.1SBT的基本操作
9.3.2SBT的效率分析
9.3.3SBT的算法实现
9.4本章习题
第10章块状链表与块状树
10.1块状链表的基本思想
10.2块状链表的基本操作
10.3块状链表的扩张
10.3.1维护区间和以及区间最值
10.3.2维护局部数据有序化
10.3.3维护区间翻转
10.4块状链表与其他数据结构的比较
10.5分块思想在树上的应用——块状树
10.6块状链表的应用举例
10.7本章习题
第11章后缀树与后缀数组
11.1后缀树的简介
11.2后缀树的定义
11.3后缀树的构建
11.3.1后缀树的朴素构建算法
11.3.2后缀树的线性时间构建算法
11.3.2.1隐式树的朴素构建
11.3.2.2扩展规则约定
11.3.2.3后缀链加速
11.3.2.4进一步加速
11.3.2.5后缀树拓展到多串的形式
11.3.2.6代码实现
11.3.2.7相关证明
11.4后缀树的应用
11.4.1字符串(集合)的精确匹配
11.4.1.1情形一
11.4.1.2情形二
11.4.1.3情形三
11.4.1.4情形四
11.4.2公共子串问题
11.4.2.1情形五
11.4.2.2情形六
11.4.2.3情形七
11.4.2.4情形八
11.4.2.5情形九
11.4.3重复子串问题
11.4.3.1情形十
11.4.3.2情形十一
11.4.3.3情形十二
11.5后缀数组的简介
11.6后缀数组的定义
11.7后缀数组的构建
11.7.1一种直接的构建算法
11.7.2倍增算法
11.7.2.1倍增算法描述
11.7.2.2倍增算法代码
11.7.3由后缀树得到后缀数组
11.7.4DC3算法和DC算法
11.7.4.1DC3算法
11.7.4.2DC算法
11.8LCP的引人
11.9后缀数组的应用
11.9.1后缀排序的直接应用
11.9.1.1Burrows-Wheeler变换
11.9.1.2多模式串的匹配
11.9.2通过引入LCP优化
11.9.2.1多模式串的匹配
11.9.2.2重复子串问题
11.9.2.3最长回文子串
11.9.2.4最长公共子串
11.9.3后缀数组的应用举例
11.10本章习题
第12章树链剖分与动态树
12.1树链剖分的思想和性质
12.2树链剖分的实现及应用
12.3动态树的初探
12.3.1动态树的常用功能
12.3.2动态树的简单情形
12.4动态树的实现
12.4.1动态树的基本操作及其实现
12.4.1.1动态树的问题模型
12.4.1.2用Splay维护实路径
12.4.2动态树操作的时间复杂度分析
12.4.2.1动态树操作的次数
12.4.2.2Splay操作的平摊时间
12.5动态树的经典应用
12.5.1求最近公共祖先
12.5.2并查集操作
12.5.3求最大流
12.5.4求生成树
12.6动态树的应用举例
12.7本章习题
致谢