数据结构
树状数组，堆
线段树
- 单点，区间
- 动态开结点
并查集
- 加了路径压缩之后不能随便撤销
- 使用启发式合并复杂度是 O(n log n)，按秩合并是 O(nα(n))。
平衡树
- treap 比较好写
- splay 比较难写， noip 也不会考这么高级的东西
- 只能说 (开了 O2 的)set 秒杀一切
dfs 序与树链剖分
非传统方法
- 点事件
- 分块
- cdq 分治
树状数组
具体思想就是要维护一个序列 a 的前缀和，我们可以维护一个辅助序列 s，使得 si = ∑j2(i-lowbit(i);i] aj，然后我们发现可以用
O(log n) 的时间维护 s。
修改 + 查询的代码一共不超过五行。
线段树
一种基于分治的数据结构，能够解决可以先分治再合并的问题。
对于线段树的理解一定要注意，线段树的核心是可合并性：一旦这个问题具有可合并性，就可以使用线段树来做。
线段树可以维护比前缀和更多的信息，但是有更大的常数（4）树状数组（1/2）。
并查集
并查集能够快速实现集合的合并，并且查询两个元素是否位于同一个集合。最经典的应用是 kruskal 算法。
常见的优化有两个：路径压缩；按秩合并。两个都加上可以实现单次操作 O(α(n)) 的时间。
如果需要维护撤销操作，就不能用路径压缩，也不能用按秩合并，因为这两个操作都是不可逆的。这个时候只能够使用启发式合并，单次操作复杂度降为 O(log n)。
平衡树
一种非常强的维护序列的数据结构，能够在 O(log n) 时间内完成很多区间操作，并且支持对区间形态的修改。经常使用的平衡树包括 splay， treap 等，动态树也是基于 splay 产生的。
NOIP 不会直接考察平衡树，而我们经常使用的是 STL 当中使用平衡树实现的容器——set, map 等 。
SET/MAP
STL 当中使用得最多的两种数据结构。
SET/MULTISET
- 维护一个有序集合（multimap 可以支持集合当中有相同的元素）
- 支持询问第 k 大，快速插入，删除
- 可以重定义比较函数
- 开了 O2 可以看作单次操作常数时间
MAP/MULTIMAP
- 维护一些有序的 pair，每个 pair 有两个参数：键值和权值按照键值排序，同一个键值只能对应一个权值（multimap 当中每个键值可以对应不止一个权值）
- 自动重载 [] 运算符
dfs 序
以 1 号点为根，对树进行一遍 dfs 遍历，在每个点进栈和出栈的时候将点加入到 dfs 序列当中，最终得到一个长度为 2n 的 dfs 序列。
这个 dfs 序列有如下几个性质：
- 长度为 2n，且每个元素恰好出现两次。
- 一棵子树对应一个区间，区间的起点和终点恰好是这棵子树的根的两次出现的位置。如果 u 在 v 的子树当中那么 u 对应的区间完全包含于 v 对应的区间。
- 点 w 在 u 到 v 的路径之上当且仅当在序列当中 u 的任意一次出现和 v 的任意一次出现所确定的区间当中点 w 出现一次。（树上莫队的基础）
树链剖分
每个点选择一个点数最多的儿子作为重儿子，这个点和重儿子之间的边称为重边，和其他儿子之间的边称为轻边。
将点重新标号，根为 1 号，之后优先标号重儿子，其他的儿子随意顺序。这样一条重链一定对应一个区间。
任意两点之间的路径一定不超过 O(log n) 条轻边。
非传统方法
非传统方法是指对于一些数据结构题，我们不使用真正意义上的高级数据结构例如线段树，平衡树等，而是使用一些算法和最基础的数据结构例如数组，链表等来解决。
点事件
- 将一整个操作序列分成一个一个小事件（称为点事件），按照一定的顺序处理这些事件，不一定是原先的事件顺序。
扫描线
- 一般和点事件一起使用
- 考虑一个二维平面，有一条无限长的线从一个方向往另一个方向扫过，按照线扫到的顺序处理关键点
cdq 分治
- 对操作序列进行分治
整体二分（省选难度）
- 如果询问操作可以二分回答，而且题目允许离线，就可以使用整体二分。
以上By：北京大学图灵班 胡家琛
PPT以后放在我的Onedrive上
文章评论