【学习笔记】FHQ Treap
前言
免责声明：本文仅用于记录学习心得、思考，仅作复习用。又由于作者文笔很烂且有些内容理解不一定正确，因此不具有一定的参考价值。
本文中用到的树生成工具
平衡树
前置知识：二叉搜索树&平衡树。
二叉搜索树（Binary Sorted Tree/Binary Search Tree, BST）是一种二叉树的树形数据结构。它的作用是能维护一段序列，可实现插入某数、删除某数、查找某数、查询最值、查询某数排名、查询某排名下的数、查询某数前驱或后继等。一般情况下大多数操作的平均复杂度均为
平衡树是一种建立在 BST 的基础上的数据结构，与普通 BST 不同的是，它引入了「平衡」的概念。对于平衡的定义，每种实现方法下均不相同。一般来说判断一棵树是否平衡，取决于其左右子树的高度或大小的差值或比值是否在某个阈值内。
平衡树是一般的 BST 的优化版本。它可以使得在大多数情况下树的形态保持相对稳定，从而使各种操作的复杂度稳定在
举个例子，若有一组数据
平衡树的实现多种多样，多数平衡树维持平衡都靠旋转操作，模板不好背且码量十分长。而接下来要提到的 FHQ Treap 就是无旋平衡树的一种。我个人认为 FHQ Treap 是所有实现当中最好理解、实现最方便且码量最小的一种，十分推荐初学者学习。
普通 Treap
前置知识：有旋 Treap。
Treap 是平衡树的一种。这个名字是由树（Tree）和堆（Heap）的英文各取前后合成而来，因此中文名也叫树堆（Treap）。顾名思义，其实现方法融合了树和堆的性质。具体地，该树上的每个结点都包含了两个信息，分别称其为权值和优先级。其中权值满足 BST 的性质，优先级满足堆的性质。一般在新建结点时默认使优先级为一个随机数。如下图是一颗大根堆 Treap，其中每个结点内逗号分隔的两个数分别为权值和优先级。
对于该树，我们利用优先级按照堆的性质使树平衡。不过需要注意的是，期望的平衡是建立在完全随机的优先级的基础上的，因此 Treap 是一种弱平衡的平衡树。此处某一子树平衡的定义较特殊，优先级满足堆的性质即为平衡。Treap 上的每个结点的期望高度均为
对于普通 Treap 其最重要的操作便是旋转。旋转分为左旋和右旋，感性理解即是将根节点右孩子或左孩子“提”上来，让自己的孩子“取代”自己的位置。如下图是一种右旋操作过程，其中每个结点内的数表示权值。
不难看出旋转后的树仍满足原本 BST 的性质。
普通 Treap 的插入、删除、查询排名、查询值以及查询前驱后继的方式与一般 BST 相同，不过是使用优先级检查树的平衡性，并用旋转操作维持树的平衡而已。此处不过多给出代码实现。
无旋 Treap
无旋 Treap 又称分裂合并 Treap。顾名思义，其操作实现不需要繁琐的旋转操作，而是只需通过两种基本操作：分裂（split）与合并（merge）即可实现大部分操作。这里需要提到的就是 FHQ Treap，在《范浩强谈数据结构》内详细给出了支持区间操作和可持久化操作的无旋 Treap 实现方法。无旋 Treap 在每个结点需要维护基础的信息有五种，分别是权值、优先级、左右孩子编号和子树大小。接下来将详细讲解 FHQ Treap 的理论操作及实现方法。每种操作的理论复杂度也均为
分裂
无旋 Treap 的分裂操作分为权值分裂与排名分裂。每种分裂的目的均是将一棵完整的 Treap 分裂成
权值分裂
权值分裂完成后
该部分的代码实现如下：
// x表示当前的结点编号，w表示要分裂的权值，l/r为分裂后两个子树的根结点编号
void split(int x,int w,int &l,int &r){// l,r引用传参，可直接修改值，避免额外的返回值
if(!x)//如果是空结点
return (void)(l=r=0);
// 对于每个结点，x表示权值，l/r表示左右孩子编号
// ...
if(t[x].x<=w){// 根据BST的性质，左小右大，因此此时要的值一定在右子树上
l=x;// 因为要去右子树了所以暂时将左点存为当前点
split(t[x].r,w,t[x].r,r);// 由上图可知右孩子的左子树上所有权值均大于自己，而又小于等于右孩子，因此先将自己右孩子查到的左值并入自己的右子树
}else{// 同上，此时值在左子树
r=x;
split(t[x].l,w,l,t[x].l);
}
// ...
}排名分裂
Rank Treap 准确来说并不满足 BST 的性质，而是维护了序列的原本顺序，即中序遍历出来的序列即为原序列而非排序后的。而按排名分裂出来的两棵 Treap 分别满足
该部分的代码实现如下：
// 同上，不过此时w变成了排名
void split(int x,int w,int &l,int &r){
if(!x)
return (void)(l=r=0);
// 此处每个结点的sz表示以其为根结点的子树大小
// ...
if(t[t[x].l].sz+1<=w)// 注意此处写法的不同，因为结点左子树大小表示排名在自己之前的结点个数，该语句表示判断是否自己的排名都比不上w，意味着要往自己右子树走
l=x,split(t[x].r,w-t[t[x].l].sz-1,t[x].r,r);// 对于此处的w传参可以这么理解，对于每个子树最左边的结点排名一定为1，因此在父树上的排名规则不适用了，需要减掉比自己小的来获取在子树上的排名
else
r=x,split(t[x].l,w,l,t[x].l);// 同上，不过此时由于本来的排名规则是从左边开始的，因此到左子树时排名规则没有变
// ...
}合并
无旋 Treap 的合并操作十分好理解，即是将两棵断裂开的树合并成一棵完整的树。具体实现也是通过递归实现，每次根据优先级考虑两个结点的父子关系，不断将两棵树以及各自子树连接在一起。该部分的代码实现如下：
// 函数返回值为合并后的树的根节点编号
int merge(int l,int r){// l/r表示要合并的两棵树的根节点编号
if(!l||!r)// 如果其中一棵为空树
return l|r;// 一棵为空树（编号为0）则合并结果就是另一棵树
if(t[l].p>t[r].p){// 按优先级判断谁是谁的长辈
t[l].r=merge(t[l].r,r);// l是r的长辈，继续递归合并右边
// ...
return l;
}else{
t[r].l=merge(l,t[r].l);// 同上
// ...
return r;
}
}插入
实现了分裂与合并两个操作，Treap 的插入也变得十分简单。
Value Treap 的插入操作非常好理解，若插入一个数
该部分的代码实现如下：
inline void newnode(int x){// 新建结点
t[++cnt].x=x;// cnt为结点计数器，既表示当前结点数量，也表示最晚新建的结点编号
t[cnt].p=rand();// 优先级设为随机
t[cnt].l=t[cnt].r=0;// 初始时没有孩子
t[cnt].sz=1;// 该节点是独立的一棵树，因此大小仅是它自己的贡献
}
void insert(int x){// x表示待插入数字
int l,r;
split(rt,x,l,r);// 按x权值分裂，全局变量rt表示整个树的根节点编号
newnode(x);// 新建x结点，即新建一棵仅包含x的树
rt=merge(merge(l,cnt),r);// 因为结点x是最后新建的结点，因此cnt表示x的结点编号
}事实上需要使用 Rank Treap 维护的序列操作中一般是在固定位置插入数，因此 Rank Treap 的插入也是类似的，在这里便不多赘述。
删除
同插入，Treap 的删除操作也很好理解。
若删除 Value Treap 上的一个数
该部分的代码实现如下：
void del(int x){// x表示待删除数字
int l,r,p;// 临时变量
split(rt,x,l,r);// 第一次分裂，此时树l内的权值均不大于x，树r的权值均大于x
split(l,x-1,l,p);// 第二次分裂，此时树l内的权值均小于x，树p内的权值均等于x
p=merge(t[p].l,t[p].r);// 注意这里的易错点，若此时直接丢弃p来合并lr的话会使得全部x都被丢弃，而这么写只会丢弃p的根结点
rt=merge(merge(l,p),r);// 将剩下的树全部合并
}Rank Treap 的删除操作一般是删除对应位置的数，与 Value Treap 几乎相同，此处不再赘述。
查询排名
FHQ Treap 维护了子树大小，这使得 Value Treap 的排名查询变得极其方便。因为对于每个结点，其左子树大小加
根据这一点，查询排名的实现过程非常简洁。若查询
int rk(int x){
int l,r,ans;// 临时记录的变量
split(rt,x-1,l,r);// 按x-1分裂
ans=t[l].sz+1;// 数的排名即是比它小的数的个数+1
rt=merge(l,r);// 分裂完后别忘了合并回去
return ans;
}对于一般的 Rank Treap 是不存在排名查询操作的，因为它并没有遵循 BST 的性质而是维护了序列的原顺序，因此此处不给出代码。
排名查值
由于 Value Treap 与 Rank Treap 对排名的定义并不相同，此处分别讨论。
Value Treap 根据排名查询值的操作可能是唯一没有用到分裂与合并的操作。它的过程是不断通过比较子树大小确定值的位置，并通过递归查找。它的实现方法与一般平衡树十分类似，便不多细讲。该部分的代码实现如下：
int kth(int x,int k){// x表示当前的结点编号，k表示要查找的排名
if(k==t[t[x].l].sz+1)// 如果k刚好等于x的排名
return x;// 找到了
if(k<=t[t[x].l].sz)// 在左子树上，因为需求排名比当前排名小
return kth(t[x].l,k);
else// 同上，此时在右子树
return kth(t[x].r,k-t[t[x].l].sz-1);// 此处k的传参解释详见Rank Treap的分裂操作
}Rank Treap 根据排名查询值的操作是基于排名分裂操作的。参考 Value Treap 的删除操作，我们发现找到一个数所在树上位置可以通过两次分裂实现。该部分的代码实现如下：
int kth(int k){// 查找排名为k的值
int l,r,p,ans;
split(rt,k,l,r);// 第一次分裂，树l内结点的排名均不大于k
split(l,k-1,l,p);// 第二次分裂，p即为找到的数的所在结点编号
ans=t[p].x;// 记录答案
rt=merge(merge(l,p),r);// 别忘了合并回去
return ans;
}