平衡树
很久以前，我立志要学习所有的平衡树，然后把每个树的学习笔记都整理到相关博客中。
而如今……
今年欢笑复明年，不知退役在眼前。
在阅读本文之前建议先学习二叉搜索树相关内容。
Fhq_Treap
原来 Treap 是一种旋转类的平衡树（即树堆），然后由防火墙范浩强神犇发明了一种不需要旋转的 Treap，凭借其短小的代码而不失精悍的功能（区间操作和可持久化）博得众人喜爱。
比起“普通平衡树”、“文艺平衡树”这种叫法，我更喜欢叫其“权值树”、“区间树”。
基本概念与储存
众所周知，BST 在极端数据（顺序插入单调值）时会退化成链，深度为 \(O(n)\)；而 heap 是一种完全二叉树，深度总是维持在 \(O(\log n)\)。
Treap 是将 BST 和 heap 结合在一起的数据结构（Treap=Tree+heap），使得整棵树的深度大致维护在 \(O(\log n)\) 左右。
不过，根据 BST 和 heap 的性质，这两个数据结构好像是冲突的，那要如何结合在一起呢？
毕竟 heap 是辅助 BST 的工具，所以，对 BST 的每个节点赋一个值 pri，使得 val 满足 BST 性质，pri 满足 heap 性质。
也就是这样：
struct Fhq_Treap{
int lc,rc;
int siz,val,pri;
}T[inf];
而这个 pri 值，随机就好。
不要不相信随机数，它可是很好用的！
可以理解为将原来的插入序列随机打乱，这样树的深度就维持在 \(O(\log n)\) 级别了。
不想感性理解的话，还有一个严谨的证明。
图示：
实现权值平衡树
了解了 Treap 的基本概念，接下来就是 Fhq_Treap 的两个 最最最重要 的操作：分裂（split）和合并（merge）。
为什么说最最最重要？因为这两个操作插入要用到，删除要用到，查询排名、k 小值、前驱后继都要用到。
分裂-split
分裂操作包含两类：按值分裂和按大小分裂。
第二种分裂方式会在下边的区间平衡树中提到。权值树中，用到的分裂方式为第一种。
split 函数包含四个参数：将原树 \(i\) 按照 \(k\) 分裂为 \(x,y\) 两棵树，其中 \(x\) 树中的 val 均 \(\le k\)，\(y\) 树中的 val 均 \(>k\)。
由于 val 满足 BST 性质，每找到一个节点，若当前节点的 val \(\le k\)，那么其左子树的 val 均 \(\le k\)，就将当前节点和左子树从 \(i\) 上拆下来，拼到 \(x\) 树上去；否则，其右子树的 val 均 \(>k\)，将当前节点和右子树从 \(i\) 上拆下来，拼到 \(y\) 树上去。
图示：
函数实现：
void split(int i,int k,int &x,int &y)
{
if(!i){x=y=0;return;}
if(T[i].val<=k)
x=i,split(T[i].rc,k,T[i].rc,y);
else y=i,split(T[i].lc,k,x,T[i].lc);
pushup(i);
}
合并-merge
为了方便实现，我们保证 \(x\) 的 val 均比 \(y\) 的 val 小。
那么合并的时候也就只需要比较两个节点的 pri 了。
既然 val 确定了，合并之后的情况就只有两种：
区别就是选择大根堆还是小根堆。
通过比较，就可以确定是将 \(x\) 的右子树与 \(y\) 合并还是将 \(x\) 与 \(y\) 的左子树合并。
至于具体的比较方案，两种应该是都可以的，毕竟堆性质的维护不会影响 BST 的性质。
但就在某天（2022 年 10 月 1 日），发生了一个玄学错误，至今未得解，可以看看这个帖子。
图示（这个图有两处错误，但可以更了解基本思想）：
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(T[x].pri<T[y].pri)
{
T[x].rc=merge(T[x].rc,y);
pushup(x);return x;
}
else
{
T[y].lc=merge(x,T[y].lc);
pushup(y);return y;
}
}
其他操作
接下来，你将明白，什么叫短小精悍！
-
pushup上边两段代码中都有
pushup操作。和 BST 相同，在权值树中，pushup的功能就是统计以当前节点为根的子树大小。void pushup(int i) { T[i].siz=T[T[i].lc].siz+T[T[i].rc].siz+1; } -
new_ k新建一个
val为k的节点。#include<random> mt19937 rnd(51205); int new_(int k) { T[++cnt].pri=rnd(); T[cnt].siz=1;T[cnt].val=k; return cnt; }mt19937 是一种神奇的随机数生成器，想深入了解的可以查阅这篇日报。
而 51205 是对我有重要意义的一个数字。
-
insert k将原树按 \(k\) 分裂，然后新建一个节点（看做一棵新的树），将三棵树合并即可。
void insert(int k) { split(rot,k,rx,ry); rot=merge(merge(rx,new_(k)),ry); }为了防止变量名冲突，我将原树树根记作 \(rot\)，所用到的临时分裂出的树的树根分别记作 \(rx,ry,rz\)，而且保证点权关系为 \(rx<ry<rz\)。
-
remove k先将 \(rot\) 按 \(k\) 分裂成 \(rx,rz\) 两树，然后将 \(rx\) 按 \(k-1\) 分裂为 \(rx,ry\) 两树。这样下来，\(ry\) 上的点的点权均为 \(k\)（如果有的话）。如果将所有 \(k\) 均删除，则直接合并 \(rx,rz\) 即可，否则先将 \(ry\) 的左右子树合并，然后再将 \(rx,ry,rz\) 合并即可。
void remove(int k) { split(rot,k,rx,rz); split(rx,k-1,rx,ry); ry=merge(T[ry].lc,T[ry].rc); rot=merge(merge(rx,ry),rz); } -
ask_kth这应该是唯一一个和旋转类平衡树一样的操作了。
但由于某些情况下不只要查询整棵树的 \(k\) 小值，所以参数有两个。
int kth(int i,int k) { while(1) { if(k==T[T[i].lc].siz+1)return T[i].val; if(k<=T[T[i].lc].siz)i=T[i].lc; else k-=T[T[i].lc].siz+1,i=T[i].rc; } } -
ask_rank k将 \(rot\) 按 \(k-1\) 分裂为 \(rx,ry\) 两棵树，那么 \(k\) 的排名就是 \(rx\) 的 \(siz+1\)。
void ask_rank(int k) { split(rot,k-1,rx,ry); wr(T[rx].siz+1),putchar('\n'); rot=merge(rx,ry); } -
ask_pre/ask_nex k本质上这两个操作是一样的，此处归为一类。
前驱：先将 \(rot\) 按照 \(k-1\) 分裂为 \(rx,ry\) 两棵树，然后 \(rx\) 中的最大值即为 \(k\) 的前驱。
后继：先将 \(rot\) 按照 \(k\) 分裂为 \(rx,ry\) 两棵树，然后 \(ry\) 中的最小值即为 \(k\) 的后继。
void ask_pre(int k) { split(rot,k-1,rx,ry); wr(kth(rx,T[rx].siz)),putchar('\n'); rot=merge(rx,ry); } void ask_nex(int k) { split(rot,k,rx,ry); wr(kth(ry,1)),putchar('\n'); rot=merge(rx,ry); }