fhq-treap

一些细节

本质是利用合并、分裂实现增、删、查。

根据用途分为两类分裂：

第一类：当作 set 一样使用，就是中序遍历就把数字排序了。分裂操作按照权值分裂。

如果

1. 根 \(\le k\)，那么左边都要归入 \(x\)，递归右边，\(x\) 换成右边（看还能接上去多少）

2. \(>k\) 同理，最后 pushup 一下。

第二类：维护序列，要对序列操作的话就按照 size 分裂，基本和上面一样，需要注意如果是情况1，进入右子树需要减去已经划入左边的 size (即 \(l_{sz}+1\)，因为你要保证左边子树是 size 个节点啊，就去右边找剩下的)。

合并方法：

1. 有一个为空，根返回另一个。
2. 按照节点生成时的优先级合并，记小的树为 \(x\)，大的树为 \(y\)（这是按照分裂时的顺序或者权值大小区分的）。 \(y\) 合到 \(x\) 的右边，或者 \(x\) 合到 \(y\) 的左边。对合到的点 pushup，返回。

接下来就是针对上面的操作的应用：（以第一类为例）

1. 插入 \(k\)（建立一个单独树，记为 \(a\)），分裂得到 \(<k,\ge k\)（记为 \(b,c\)），合并 \(b,a\)，再跟 \(c\) 合并。

2. 删除，先分裂得到 \(\le k,>k\)（记为 \(a,b\)），再分裂 \(a\) 得到 \(\le k-1,=k\)（记为 \(a,c\)），把 \(c\) 的两个儿子合并删去根，，合并 \(a,c\)，再跟 \(b\) 合并。

3. 排名查询：分裂利用size

4. 查询排名对应的数：从根开始每次考虑往左还是往右找

5. 前驱：分裂然后小的里一直往大的走

6. 后继：分裂然后大的里一直往小的走

第二类类比一下。