高级数据结构
发布时间 2024-01-08 14:11:35作者: 牛肉爱吃dks
并查集
- 普通并查集的应用只需要注意边带权的转化。
- 合并方式优化按深度大小要更合理一些。
- 可持久化并查集：把原来的 \(fa\) 数组变成可持久化数组，注意不要路径压缩，直接按秩合并即可。
- 可撤销并查集：还是不要路径压缩，只用按秩合并，每次记录一下修改了什么，撤销的时候倒回去就行。只需要撤销的时候就不需要用可持久化了。
- 并查集的本质是树（森林），所以有时候可以考虑转化为树上问题解决。
- Examples
树状数组
- 树状数组的基础题直接套板子就行了，但是更复杂的应用需要回到树状数组的本质（编号方式）去思考，比如解决不满足线性性的最值问题。
- 解决像区间修改区间查询这类问题需要一些转化，变为若干可以用树状数组解决的问题。
- 树状数组可以和倍增思想结合，进行树状数组上二分。
线段树
- 普通线段树不要为了省空间开两倍，不然怎么死的都不知道。开四倍是因为极端情况会刚好多出一个点再最后一行。
- 考点经常在懒标记和信息维护上，线段树只是糖衣。
- 吉司机线段树：记录区间的最大值和次大值，两者都要修改时直接递归到儿子。解决区间最值区间修改一类的问题。
- 线段树非常适合做区间合并，可以合并左右儿子区间对称的信息，也可以合并单向的信息（比如从左往右的）。
- 找思路别忘了扫描线。
- 如果一道题要用到树套树，那最好还是再想想有没有忽略一些别的信息或者思考一下别的方法，真正要用到树套树的题挺少的（部分分除外）。
- 线段树上二分比普通二分+线段树查询少一个 \(\log\)。
可持久化线段树
- 经常在把一段区间截出来后搭配线段树上二分。
- 区间修改的主席树其实没有多多少复杂度。可以这样思考：线段树的区间操作是 \(O(\log n)\) 的，主席树的区间修改时的遍历方式其实和线段树的区间操作类似，也就是 \(O(\log n)\) 的，增加的点数也是 \(O(\log n)\) 的，和单点修改没啥差别，只是多了一个标记永久化。
分块与莫队算法
- 优美的暴力。
- 考虑一种基于分块思想优化：尽量将每种操作的复杂度平均。例如最简单的， \(O(1)\) 修改，\(O(n)\) 询问，可以尝试变成 \(O(\sqrt n)\) 修改 \(O(\sqrt n)\) 询问。还有不太容易想到的，\(O(\log n)\) 和 \(O(\sqrt n \log n)\) 平均成 \(O(\sqrt n)\) 等。常用值域分块实现。
- 大分块的考点常在信息维护上。
- 莫队解决的时序列上的问题，如果是树上问题可以尝试用 DFS 序、欧拉序、括号序等转化。
块状链表
简单树上问题
- 树的重心常在点分治和点分树中用到
- 树的直径用两次 DFS 求是最基础的，但是如果加上一些修改就需要从树形 dp 的方向思考了。
LCA
- 倍增求 LCA 有时会顺带倍增维护一些其他的信息比如求链上最值之类的。
- tarjan 求 LCA：离线求 LCA，遍历树，到点 \(u\) 时如果 \(v\) 被遍历过，那么 \(lca(u,v)\) 就是 \(v\) 祖先中深度最大的没有被回溯的点。
- 没有办法离线询问有比较多的情况可以用欧拉序 + RMQ 求 LCA。
- 理论上来说树剖求 LCA 会比倍增快一点，虽然时间复杂度时一样的。