可持久化平衡树

前置知识

OI 常用的可持久化平衡树 一般就是 可持久化无旋转 Treap 所以推荐首先学习

无旋转 Treap。

思想/做法

对于非旋转 Treap，可通过 Merge 和 Split 操作过程中复制路径上经过的节点（一般在 Split 操作中复制，确保不影响以前的版本）就可完成可持久化。

对于旋转 Treap，在复制路径上经过的节点同时，还需复制受旋转影响的节点（若其已为这次操作中复制的节点，则无需再复制），对于一次旋转一般只影响两个节点，那么不会增加其时间复杂度。

上述方法一般被称为 path copying。

「一切可支持操作都可以通过 Merge Split Newnode Build 完成」，而 Build 操作只用于建造无需理会，Newnode（新建节点）就是用来可持久化的工具。

我们来观察一下 Merge 和 Split，我们会发现它们都是由上而下的操作！

因此我们完全可以 参考线段树的可持久化操作 对它进行可持久化。

可持久化操作

可持久化 是对 数据结构 的一种操作，即保留历史信息，使得在后面可以调用之前的历史版本。

对于 可持久化线段树 来说，每一次新建历史版本就是把 沿途的修改路径 复制出来

那么对可持久化 Treap（目前国内 OI 常用的版本）来说：

在复制一个节点 （ 节点的第 个版本）的新版本 （ 节点的第 个版本）以后：

• 如果某个儿子节点 不用修改信息，那么就把 的指针直接指向 （ 节点的第 个版本）即可。
• 反之，如果要修改 ，那么就在 递归到下层 时 新建 （ 节点的第 个版本）这个新节点用于 存储新的信息，同时把 的指针指向 （ 节点的第 个版本）。

可持久化

需要的东西：

• 一个 struct 数组 存 每个节点 的信息（一般叫做 tree 数组）；（当然写 指针版 平衡树的大佬就可以考虑不用这个数组了）

• 一个 根节点数组，存每个版本的树根，每次查询版本信息时就从 根数组存的节点 开始；

• split() 分裂 从树中分裂出两棵树

• merge() 合并 把两棵树按照随机权值合并

• newNode() 新建一个节点

• build() 建树

Split

对于 分裂操作，每次分裂路径时 新建节点 指向分出来的路径，用 std::pair 存新分裂出来的两棵树的根。

split(x,k) 返回一个 std::pair;

表示把 为根的树的前 个元素放在 一棵树 中，剩下的节点构成在另一棵树中，返回这两棵树的根（first 是第一棵树的根，second 是第二棵树的）。

• 如果 的 左子树 的 ，那么 直接递归进左子树，把左子树分出来的第二颗树和当前的 右子树 合并。
• 否则递归 右子树。

Merge

merge(x,y) 返回 merge 出的树的根。

同样递归实现。如果 x 的随机权值>y 的随机权值，则 merge(x_{rc},y)，否则 merge(x,y_{lc})。

例题

就是 普通平衡树 一题的可持久化版，操作和该题类似。

只是使用了可持久化的 merge 和 split 操作。

推荐的练手题

1. 「Luogu P3919」可持久化数组（模板题）

2. 「Codeforces 702F」T-shirt

3. 「Luogu P5055」可持久化文艺平衡树