安塔的全局平衡二叉树学习笔记

# 前言 切题连 WA，不想打代码，就顺手学一下算法。正巧我有个朋友在学全局平衡二叉树，然后我就想学一下，然后不到十分钟会了，于是就有了这篇博客。 # 前置知识 + [动态DP](https://www.luogu.com.cn/problem/P4719) （只要知道动态 DP 在干什么，学会树链剖分实现即可，~~别看是黑题其实不难~~） + 不需要任何高级的平衡树知识（当然基础知识还是要的）。 # 树剖为什么慢 首先我们发现线段树的可调整性太差，节点数给死了树高就定死了，根本没法调整，所以我们第一步是抛弃线段树换用平衡树。 这里假设读者都会了平衡树维护序列的相关知识，不会的可以去 [文艺平衡树](https://www.luogu.com.cn/problem/P3391) 看一眼，不需要学习 Splay。简单说一下，如果将平衡树中的每个点对应为序列的每个元素，然后中序遍历顺序是原序列顺序，那么平衡树中的每一个子树都是序列的一个区间。  首先，如果按照重链为中心的角度看待树剖后的图（重链上数字为结点的 DFS 序），可以看成这样：  这里的每条重链都用一颗平衡二叉树维护，结点先是从某个位置开始，一步一步跳到根，然后从根杀到另外一个重链的平衡二叉树的某个位置，再继续往上跳，直到跳到根节点。 将每个重链用一个平衡二叉树维护，那么整个修改过程可以视作在这棵树上往上跳：  这里所有的二叉树都是绝对平衡的，在某一个长度为 $n$ 的重链上跳的次数是 $\Theta(\log n)$，但是一共要最多 $\Theta(\log n)$ 个重链，最终时间复杂度是 $\Theta(\log^2 n)$。 问题在哪里呢？因为我们的二叉树太平衡了。 # 全局平衡二叉树 很显然，我们有优化的地方。 比如说，如果一个重链的二叉树的某一个结点上面挂了一大堆轻儿子，那么就可以把这个节点的深度适当抬浅，那么所有在这些轻儿子里面的修改都能少跳几下。  （最深的点只需要跳 4 下，比上面 7 下优化了很多） 利用 Splay 的思想进行这个抬浅操作，就是 LCT 保证时间复杂度为 $\Theta(\log n)$ 的方法。具体证明需要用到势能分析，不展开。 但是我们这个是静态的啊！动态 DP 又不需要调整树结构，树的结构是完全静态的！ 对于只需要修改和查询的序列问题，因为序列是静态的，就可以直接建立一颗平衡的二叉树（其实相当于线段树），这样不仅时间复杂度保证为 $\Theta(\log n)$，码量也低，常数也小。 那么，在做动态 DP 的时候，也可以用类似的思路，就不用把 LCT 搬出来杀鸡用牛刀了。 这里的目标是要建树并使最终深度最小化。最终的深度定义为每一个点到根所需要跳的步数，这里的跳包括在重边二叉树中的跳，也包括在轻边上的跳。 再放一遍某张图方便理解下面的一段：  按照“尽量均分”的策略，在每一次选择根的时候，只需要选择那个能让根下的子树们（包括两个重儿子和一些轻儿子）点数最相近的根就好。实际上就是递归选择重链上的一个带权重心，不赘述。 # 时间复杂度 每次询问的时间复杂度是 $\Theta(\log n)$，因为每次选根我们都让他的子树们尽量均分，这颗全局平衡二叉树的深度是 $\Theta(\log n)$。 建树的时间复杂度证明也很简单。因为在处理某一个重链的过程中，点被扫描的次数相当于这个点在重链排成的二叉树上的深度，而这个深度显然不会超过全局的深度 $\Theta(\log n)$，最后时间复杂度就是 $\Theta(n\log n)$，在所有点形成一条链的时候取到。 # 拓展 有没有 $\Theta(n)$ 的建树法？ 【咕咕咕】 # 参考资料 图均由 [draw.io](www.draw.io) 制作。 + [动态DP之全局平衡二叉树 -T\_Y\_P\_E](https://www.cnblogs.com/T-Y-P-E/p/10595785.html) + [DP也要搞动态，动态DP与全局平衡二叉树详(lue)解 -敌敌畏58](https://www.cnblogs.com/zhangjianjunab/p/12187184.html)