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

木木！ · 2020-03-21 22:31:30 · 个人记录

前言

切题连 WA，不想打代码，就顺手学一下算法。正巧我有个朋友在学全局平衡二叉树，然后我就想学一下，然后不到十分钟会了，于是就有了这篇博客。

首先我们发现线段树的可调整性太差，节点数给死了树高就定死了，根本没法调整，所以我们第一步是抛弃线段树换用平衡树。

这里假设读者都会了平衡树维护序列的相关知识，不会的可以去文艺平衡树看一眼，不需要学习 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 制作。