1. 概念
Treap 树是维护二叉查找树平衡的一种方法。它的核心思想是给每个结点设置一个随机的优先级，使它成为一个堆，即父亲的优先级一定小于（或大于）孩子的优先级。大于则为大根堆，小于则为小根堆。本节使用的是小根堆。这样就可以实现概率上的平衡。
下图是一棵 Treap 树的建树方法。
其中字母是键值，数字是优先级。可以发现，建好树后，中序遍历键值递增，且按优先级满足大根堆。
2. 旋转法
旋转法是 Treap 树调节平衡的经典方法。它的示意图如下：
代码如下：
void rotate(int &u,bool le){
/*旋转节点为u，le为是否左旋*/
int k;
/*k为新的根节点*/
if(le){
k=t[u].rs;
t[u].rs=t[k].ls;
t[k].ls=u;
}else{
k=t[u].ls;
t[u].ls=t[k].rs;
t[k].rs=u;
}
t[k].sz=t[u].sz;
/*更新k子树大小*/
pushup(u);
/*更新u子树大小*/
u=k;
/*更新根节点*/
}
通过旋转法，可以实现以下操作：
- 插入结点 \(k\)
根据权值，找到一个合适的位置插入结点 \(k\)，并为它分配优先级。接下来只要它的优先级比它的父亲小，就将它向上调整。可以用旋转法来调整。
调整的过程如下图：
代码如下：
void insert(int &u,int k){
/*插入结点k，现在的子树是u*/
if(!u){
/*这里没有结点，可以直接插入*/
newnode(k);
/*新建节点*/
u=tot;
return;
}
if(k<t[u].vl){
insert(t[u].ls,k);
/*插入左子树*/
if(t[t[u].ls].pri<t[u].pri){
/*左儿子的优先级更小，就右旋*/
rotate(u,0);
}
}else{
insert(t[u].rs,k);
/*插入右子树*/
if(t[t[u].rs].pri<t[u].pri){
/*右儿子的优先级更小，就左旋*/
rotate(u,1);
}
}
pushup(u);
/*更新子树大小*/
}
- 删除结点 \(k\)
如果 \(k\) 是叶子节点，直接删除。
如果 \(k\) 只有一个子树，就将子树移到 \(k\) 的位置，直接删除。
否则说明它有两个子节点。将这两个子节点中优先级更小的那个旋转上来，这样 \(k\) 就向下移动一层。直到 \(k\) 成为叶子节点后就可以直接删除了。
代码如下：
void erase(int &u,int k){
/*删除结点k，此时子树为u*/
if(k==t[u].vl){
if(!t[u].ls&&!t[u].rs){
u=0;return;
/*叶子节点直接删除*/
}else if(!t[u].ls||!t[u].rs){
u=t[u].ls+t[u].rs;return;
/*有一个子树为空，直接删除*/
}else if(t[t[u].ls].vl<t[t[u].rs].vl){
rotate(u,0);erase(t[u].rs,k);
/*左儿子优先级小，右旋，继续递归删除*/
}else{
rotate(u,1);erase(t[u].ls,k);
/*右儿子优先级小，左旋，继续递归删除*/
}
}else if(k<t[u].vl){
erase(t[u].ls,k);
/*在左子树上，继续递归删除*/
}else{
erase(t[u].rs,k);
/*在右子树上，继续递归删除*/
}
pushup(u);
/*更新子树大小*/
}
- 求 \(k\) 的排名
排名为比 \(k\) 小的数的个数加一。从根节点开始递归，如果这个数大于等于 \(k\)，就递归左子树。否则答案为递归右子树的答案加左子树的大小加 \(1\)。
代码如下：
void rank(int u,int k,int &ret){
/*查询比k小的数的个数，此时子树为u，最后答案为ret*/
if(!u){
ret=0;
}else if(k<=t[u].vl){
/*比k小的数都在左子树*/
rank(t[u].ls,k,ret);
}else{
/*在右子树上*/
rank(t[u].rs,k,ret);
ret+=t[t[u].ls].sz+1;
/*右子树上的排名+左子树大小+1*/
}
}
- 求排名为 \(k\) 的数
从根结点开始递归，如果这个结点左子树的大小加一等于 \(k\)，那么答案就为这个结点的权值。否则如果 \(k\) 小于这个点左子树的大小加一，就在左子树上找，否则在右子树上找。
代码如下：
void kth(int u,int k,int &ret){
/*查询排名为k的数，此时子树为u，最后答案为ret*/
if(k==t[t[u].ls].sz+1){
/*找到了*/
ret=t[u].vl;
}else if(k<t[t[u].ls].sz+1){
/*在左子树上*/
kth(t[u].ls,k,ret);
}else{
/*在右子树上*/
kth(t[u].rs,k-t[t[u].ls].sz-1,ret);
}
}
- 求 \(k\) 的前驱
从根节点开始递归。
如果这个点的权值大于等于 \(k\)，就在左子树上找。否则在左子树上找，如果没找到，那么这个点就是答案。
代码如下：
void pre(int u,int k,int &ret){
/*求k的前驱，此时子树为u，最后答案为ret*/
if(!u){
ret=FAIL;return;
}
if(k<=t[u].vl){
/*一定在左子树上*/
pre(t[u].ls,k,ret);
}else{
/*可能是这个点，也可能在右子树*/
pre(t[u].rs,k,ret);
/*先在右子树上找*/
if(ret==FAIL){
/*如果没找到，答案就是这个点*/
ret=t[u].vl;
}
}
}
- 求 \(k\) 的后继
从根节点开始找。
如果这个点的权值小于等于 \(k\)，就在右子树上找。否则在左子树上找，如果没找到，那么这个点就是答案。
代码如下：
void suc(int u,int k,int &ret){
/*求k的后继，此时子树为u，最后答案为ret*/
if(!u){
ret=FAIL;return;
}
if(k>=t[u].vl){
/*一定在右子树上*/
suc(t[u].rs,k,ret);
}else{
/*可能是这个点，也可能在左子树*/
suc(t[u].ls,k,ret);
/*先在左子树上找*/
if(ret==FAIL){
/*如果没找到，答案就是这个点*/
ret=t[u].vl;
}
}
}