打模拟赛 ⇨ 写主席树TLE了 ⇨ 看正解是可持久化平衡树 ⇨ 原来我还没写过可持久化平衡树 ⇨ 现学
# 平衡树的可持久化
可持久化就是「不修改原始信息,将新版本的信息新建节点储存」。
可持久化我们熟悉啥?众所周知的线段树可以可持久化,因为每次修改只会改一条从根到叶子的链,树高是 $\mathcal{O}(\log n)$ 的,所以每次只会增加这么多点数。
那平衡树似乎也是这么个道理,树高是 $\mathcal{O}(\log n)$ 的,每次也是修改根到叶子的一条链。
但是有个问题,其实线段树方便可持久化的另一原因是 它的结构(树形)不会改变。
虽然并不是说树形改变就不能可持久化(反正听说 splay 什么也是可以可持久化的),但若是有旋转操作的平衡树,可持久化就相当麻烦。于是我们说的可持久化平衡树,大多数时候就是 非旋Treap 的可持久化。
# 可持久化非旋Treap
非旋 Treap 最重要的两个操作当然就是 split 和 merge。其他操作都不会 直接地改变树形,因此我们只考虑 split 和 merge 的可持久化,以及与之密切相关的 insert 和 delete 操作。
- split & merge
先看 split,这个比较简单,因为不能改变原始信息 —— 也就是不能直接把根 $u$ 给拆开。那么我们就复制一个节点 $u’$,把 $u’$ 拆开即可。伪代码如下:
点击展开/折叠伪代码
$$ \begin{array}{ll} 1&\mathbf{Input.}\text{ 树 }x\text{ 和整数 }key\\ 2&\mathbf{Output.}\ (l,r)\text{ 表示将树 }x\text{ 分成两部分,根分别为 }l,r\text{ 其中 }l\text{ 的元素}\\ &\textbf{不大于 }key\text{ 而 }r\text{ 的元素}\textbf{严格大于 }key\\ 3&\mathbf{Method.}\\ 4&\mathbf{function}\ \operatorname{split}(x,key)\\ 5&\qquad\mathbf{if}\ x=\mathrm{null}\\ 6&\qquad\qquad\mathbf{return}\ (\mathrm{null,null})\\ 7&\qquad \mathrm{copy}\ y\ \mathrm{from}\ x\\ 8&\qquad\mathbf{if}\ key_y\le key\\ 9&\qquad\qquad(l,r)\gets \operatorname{split}(rson_y,key)\\ 10&\qquad\qquad rson_y\gets l\\ 11&\qquad\qquad l\gets y\\ 12&\qquad\mathbf{else}\\ 13&\qquad\qquad(l,r)\gets \operatorname{split}(lson_y,key)\\ 14&\qquad\qquad lson_y\gets r\\ 15&\qquad\qquad r\gets y\\ 16&\qquad\mathbf{return}\ (l,r) \end{array} $$然后是 merge,其实 merge 本身可持久化也非常简单,只需要把合并得到的节点新建节点就可以了。问题在于 —— 我们真的需要对 merge 新建节点吗?
在比较常见的平衡树操作中,split 和 merge 往往是成对出现的,一般就是把原树 split 过后进行一些操作再 merge 回来。如果 split 和 merge 都新建节点,那么节点数就会有 $\times2$ 的常数。
关于这一点,我比较认同这篇博客:可持久化平衡树详解及实现方法分析。我个人的理解如下:
- 由于 merge 和 split 成对出现,那么 merge 时的版本应该和 split 的版本是一样的(都是「当前版本」);
- 如果 merge 时合并的节点都是当前版本的节点,那么就不需要新建点。
我们不妨观察 split 的代码实现。函数返回的是当前这棵树按照键值 $key$ 分成的两棵树的根节点,而这些根节点都是我们新建的。
简称 split 得到的 $\le key$ 的树为「左树」,另一棵为「右树」。
结合下图可以发现,左树最右侧的一条链 和 右树最左侧的一条链 都是新建的节点:
如果 merge 的时候也是合并的这些新建的节点就好了。
若将相同键值储存在同一个节点上记录 count,这样 split 和 merge 的方案是唯一的,所以 merge 的一定也是这些节点。
这里其实有一点不是很理解,就是把相同键值也分开存会有什么问题……如果有读者知道,欢迎在评论区中提出
- insert & delete
注意到我们把相同键值储存在同一个节点中了,insert 时就不能直接新建节点 $key$,把原树按 $key$ split 开再 merge 回去。
于是先直接在平衡树上找到 $key$ 这个点(如果有的话),然后将根到这个节点的路径全部新建节点,更新 count 和 size。
否则就按键值 split 开,新建节点 $key$ 通过 merge 插入在左树和右树中间。新建的节点当然也是「当前版本」的节点,根据上面的论证,merge 不需要新建节点。
delete 同理,先找 $key$ 对应的节点,若存在大于等于两个 $key$,则和 insert 一样,复制一份根到该节点的链更新 count 和 size。否则删除过后这个节点就不见了,将原树 split 两遍就可以把这个节点单独挑出来,剩下的直接 merge 就可以了。
# 源代码
1 | /*Lucky_Glass*/ |