WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
可持久化平衡树 - 数据结构
Split-Merge Treap * * * ## 对于无旋 Treap 的提示 看楼上的 [Treap 词条](#) **OI 常用的可持久化平衡树** 一般就是 **可持久化无旋转 Treap** 所以推荐首先学习楼上的 **无旋转 Treap** ## 思想/做法 对于非旋转 Treap,可通过 **Merge** 和 **Split** 操作过程中复制路径上经过的节点(一般在 **Split** 操作中复制,确保不影响以前的版本)就可完成可持久化。 对于旋转 Treap,在复制路径上经过的节点同时,还需复制受旋转影响的节点(若其已为这次操作中复制的节点,则无需再复制),对于一次旋转一般只影响两个节点,那么不会增加其时间复杂度。 上述方法一般被称为 path copying。 「一切可支持操作都可以通过 **Merge Split Newnode Build** 完成」,而 **Build** 操作只用于建造无需理会, **Newnode** (新建节点)就是用来可持久化的工具。 我们来观察一下 **Merge** 和 **Split** ,我们会发现它们都是由上而下的操作! 因此我们完全可以 **参考线段树的可持久化操作** 对它进行可持久化。 ## 可持久化操作 **可持久化** 是对 **数据结构** 的一种操作,即保留历史信息,使得在后面可以调用之前的历史版本。 对于 **可持久化线段树** 来说,每一次新建历史版本就是把 **沿途的修改路径** 复制出来 那么对可持久化 Treap(目前国内 OI 常用的版本)来说: 在复制一个节点 $X_{a}$ ( $X$ 节点的第 $a$ 个版本)的新版本 $X_{a+1}$ ( $X$ 节点的第 $a+1$ 个版本)以后: - 如果某个儿子节点 $Y$ 不用修改信息,那么就把 $X_{a+1}$ 的指针直接指向 $Y_{a}$ ( $Y$ 节点的第 $a$ 个版本)即可。 - 反之,如果要修改 $Y$ ,那么就在 **递归到下层** 时 **新建** $Y_{a+1}$ ( $Y$ 节点的第 $a+1$ 个版本)这个新节点用于 **存储新的信息** ,同时把 $X_{a+1}$ 的指针指向 $Y_{a+1}$ ( $Y$ 节点的第 $a+1$ 个版本)。 ## 可持久化 需要的东西: - 一个 struct 数组 存 **每个节点** 的信息(一般叫做 tree 数组);(当然写 **指针版** 平衡树的大佬就可以考虑不用这个数组了) - 一个 **根节点数组** ,存每个版本的*树根*,每次查询版本信息时就从 **根数组存的节点** 开始; - split() 分裂 **从树中分裂出两棵树** - merge() 合并 **把两棵树按照随机权值合并** - newNode() 新建一个节点 - build() 建树 ### Split 对于 **分裂操作** ,每次分裂路径时 **新建节点** 指向分出来的路径,用 `std::pair` 存新分裂出来的两棵树的根。 `split(x,k)` 返回一个 `std::pair` ; 表示把 $_x$ 为根的树的前 $k$ 个元素放在 **一棵树** 中,剩下的节点构成在另一棵树中,返回这两棵树的根(first 是第一棵树的根,second 是第二棵树的)。 - 如果 $x$ 的 **左子树** 的 $key ≥ k$ ,那么 **直接递归进左子树** ,把左子树分出来的第二颗树和当前的 x **右子树** 合并。 - 否则递归 **右子树** 。 ```cpp static std::pair
_split(int _x, int k) { if (_x == 0) return std::make_pair(0, 0); else { int _vs = ++_cnt; // 新建节点(可持久化的精髓) _trp[_vs] = _trp[_x]; std::pair
_y; if (_trp[_vs].key <= k) { _y = _split(_trp[_vs].leaf[1], k); _trp[_vs].leaf[1] = _y.first; _y.first = _vs; } else { _y = _split(_trp[_vs].leaf[0], k); _trp[_vs].leaf[0] = _y.second; _y.second = _vs; } _trp[_vs]._update(); return _y; } } ``` ### Merge int merge(x,y) 返回 merge 出的树的根。 同样递归实现。如果 **x 的随机权值** > **y 的随机权值** ,则 $merge(x_{rc},y)$ ,否则 $merge(x,y_{lc})$ 。 ```cpp static int _merge(int _x, int _y) { if (_x == 0 || _y == 0) return _x ^ _y; else { if (_trp[_x].fix < _trp[_y].fix) { _trp[_x].leaf[1] = _merge(_trp[_x].leaf[1], _y); _trp[_x]._update(); return _x; } else { _trp[_y].leaf[0] = _merge(_x, _trp[_y].leaf[0]); _trp[_y]._update(); return _y; } } } ``` ## Luogu P3835 可持久化平衡树 ### 题目背景 本题为题目 **普通平衡树** 的可持久化加强版。 数据已经经过强化 ### 题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本): 1. 插入 x 数 2. 删除 x 数(若有多个相同的数,因只删除一个,如果没有请忽略该操作) 3. 查询 x 数的排名(排名定义为比当前数小的数的个数 + 1。若有多个相同的数,因输出最小的排名) 4. 查询排名为 x 的数 5. 求 x 的前驱(前驱定义为小于 x,且最大的数,如不存在输出 -2147483647) 6. 求 x 的后继(后继定义为大于 x,且最小的数,如不存在输出 2147483647) 和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本(操作 3, 4, 5, 6 即保持原版本无变化)。 每个版本的编号即为操作的序号(版本 0 即为初始状态,空树) ### 输入格式 第一行为 n,表示操作的个数,下面 n 行每行有两个数 opt 和 x,opt 表示操作的序号 $(1 \leq x \leq le6)$ 。 ### 输出格式 对于操作 3,4,5,6 每行输出一个数,表示对应答案。 ## 题解简述 就是 **普通平衡树** 一题的可持久化版,操作和该题类似…… 只是使用了可持久化的 merge 和 split 操作 ## 推荐的练手题 1. [「Luogu P3919」可持久化数组(模板题)](https://www.luogu.com.cn/problem/P3919) 2. [「Codeforces 702F」T-shirt](http://codeforces.com/problemset/problem/702/F) 3. [「Luogu P5055」可持久化文艺平衡树](https://www.luogu.com.cn/problem/P5055)