平衡树学习笔记
前置芝士
平衡树的前置芝士：全局平衡二叉树。
平衡树
平衡树是一种基于二叉搜索树的数据结构。
满足:左儿子 \(<\) 根 \(<\) 右儿子。
也就是一切小于根节点的在左边，一切大于根节点的在右边。
这样想要查找一个节点的位置时间复杂度就是 \(O(\log n)\)。
平衡树主要有三种：Splay，Treap，无旋Treap。
还有其他的像替罪羊树，红黑色。
Splay
Splay 由于 LCT 滚出 OI 的原因也跟着少用了。
但是本人以为还是 Splay 比较好用的。
核心操作
Splay 的基本操作就是将BST旋转，分左旋和右旋(其实都差不多)。
旋转的要求：在不改变原有的中序遍历的前提下改变树的结构。
简化一下：把儿子节点与父亲节点的身份互换，且有BST性质。
旋转 \(zig(x)\),\(zag(x)\) 如下图：
具体描述
设要旋转的节点为 \(x\)，它的父亲为 \(y\)，\(y\) 的父亲为 \(z\)。
- 将 \(y\) 的左儿子设为 \(x\) 的右儿子
- 若 \(x\) 的右儿子存在，将 \(x\) 的右儿子的父亲设为 \(y\)
- 将 \(x\) 的右儿子设为 \(y\)
- 将 \(y\) 的父亲设为 \(x\)
- 将 \(x\) 的父亲设为 \(z\)
- 若 \(z\) 存在，将 \(z\) 的某个子节点（原来 \(y\) 所在的子节点）设为 \(x\)
双旋操作
在 Splay 中，每加入一个新的节点就需要把它旋转到根。
设当前需旋转的节点为 \(x\)，节点的旋转可分为以下三种：
\(1.\)\(x\) 的父亲是根，这时直接旋转即可。
\(2.\)父亲和 \(x\) 的儿子同侧（即同为左儿子或同为右儿子），这时先旋转父亲，再旋转 \(x\)。
\(3.\)父亲和 \(x\) 的儿子不同侧，这时将 \(x\) 旋转两次。
如下图：
时间复杂度
对于这个时间复杂度的分析，我们需要用一下势能分析。
设\(siz(x)\) 表示以 \(x\) 为根节点的子树大小。
\(\phi(x)\) 表示在进行 \(x\) 次操作后的势能函数。
\(c(x)\) 表示时间的时间复杂度。
\(a(x)\) 表示均摊的时间复杂度。
所以根据定义，我们可以得出：
\(\phi(x)=\log(siz(x))\)
\(a(x)=c(x)+\phi(x)-\phi(x-1)\)
即 \(\sum a(x)=\phi(n)-\phi(0)+\sum c(x)\)
因为根据 \(\phi(x)=\log(siz(x))\)，所以现在肯定有:\(|\phi(n)-\phi(0)|\le n\log n\)
考虑每一次的 \(\Delta\phi\)
对于zig:
对于zig-zig
那么Splay到根的均摊代价为 \(O(logn)\)，\(zig\) 只有一次操作，所以只会使均摊代价增加\(k\)
再算上 \(\phi(n)-\phi(0)=n\log n\)
所以总时间复杂度为 \(O(n\log n)\)。
操作
讲了核心操作和时间复杂度后，我们来看看它可以支持的操作。
注：由于我们只能保证 Splay 本身的时间复杂度，所以我们就必须只能通过旋转来实现一些操作。
查询数值
给定一个数 \(k\)，查询排名为 \(k\) 的数。
- 若 \(k\) 小于等于左子树大小，就向左子树走
- 否则，将 \(k\) 先减去左子树大小和当前节点的 \(cnt\)，使得 \(k\), 等于在右子树中的排名。然而若 \(k\) 小于等于 \(0\)，说明已经找到，进行旋转，并返回当前节点权值。
查询 \(x\) 的前驱和后继
我们先将 \(x\) 节点旋转到根节点。
- 前驱：就是 \(x\) 左子树中最右边的节点。
- 后继：就是 \(x\) 右子树中最左边的节点。
删除节点 \(x\)
我们需要先将 \(x\) 旋转到根节点，从而去得到它的前驱和后继。
然后将前驱旋转到根，再将后继旋转到根，就会得到下图：
直接把 \(x\) 删去即可。
查询区间 \(\left[l,r\right]\)
我们需要将 \(l\) 的前驱旋转到根，再将 \(r\) 的后继旋转到根节点，点像删除操作。
而 \(l\) 前驱的右子树就是整个 \([l,r]\) 区间了。