转载自https://www.cnblogs.com/fengzhiyuan/articles/7994428.html，转载请注明出处
Treap 简介
Treap 是一种二叉查找树。它的结构同时满足二叉查找树（Tree）与堆（Heap）的性质，因此得名。Treap的原理是为每一个节点赋一个随机值使其满足堆的性质，保证了树高期望 O(log2n) ，从而保证了时间复杂度。
Treap 是一种高效的平衡树算法，在常数大小与代码复杂度上好于 Splay。
Treap 的基本操作
现在以 BZOJ 3224 普通平衡树为模板题，详细讨论 Treap 的基本操作。
1.基本结构
在一般情况下，Treap 的节点需要存储它的左右儿子，子树大小，节点中相同元素的数量（如果没有可以默认为1），自身信息及随机数的值。
struct node{
int l, r, v, siz, rnd, ct;
}d[];l 为左儿子节点编号， r 为右儿子节点编号， v 为节点数值， siz 为子树大小， rnd 为节点的随机值， ct为该节点数值的出现次数（目的为将所有数值相同的点合为一个）。2.关于随机值
随机值由 rand() 函数生成， 考虑到 <cstdlib> 库中的 rand() 速度较慢，所以在卡常数的时候建议手写 rand() 函数。
inline int rand(){
static int seed = ;
return seed = (int)((((seed ^ ) + 19260817ll) * 19890604ll) % );
}其中 seed 为随机种子，可以随便填写。
3.节点信息更新
节点信息更新由 update() 函数实现。在每次产生节点关系的修改后，需要更新节点信息（最基本的子树大小，以及你要维护的其他内容）。
时间复杂度 O(1) 。
inline void update(int k){
d[k].siz = d[lc].siz + d[rc].siz + d[k].ct;
}4.「重要」左旋与右旋
左旋与右旋是 Treap 的核心操作，也是 Treap 动态保持树的深度的关键，其目的为维护 Treap 堆的性质。
下面的图片可以让你更好的理解左旋与右旋：
下面具体介绍左旋与右旋操作。左旋与右旋均为变更操作节点与其两个儿子的相对位置的操作。
「左旋」为将作儿子节点代替根节点的位置， 根节点相应的成为左儿子节点的右儿子（满足二叉搜索树的性质）。相应的，之前左儿子节点的右儿子应转移至之前根节点的左儿子。此时，只有之前的根节点与左儿子节点的 siz 发生了变化。所以要 update() 这两个节点。
「右旋」类似于「左旋」，将左右关系相反即可。
时间复杂度 O(1) 。
void rturn(int &k){ //右旋
int t = d[k].l; d[k].l = d[t].r; d[t].r = k;
d[t].siz = d[k].siz; update(k); k = t;
}
void lturn(int &k){ //左旋
int t = d[k].r; d[k].r = d[t].l; d[t].l = k;
d[t].siz = d[k].siz; update(k); k = t;
}
5.节点的插入与删除
节点的插入与删除是 Treap 的基本功能之一。
「节点的插入」是一个递归的过程，我们从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子；
相等则直接在把当前节点数值的出现次数 +1 ，跳出循环即可。如果当前访问到了一个空节点，则初始化新节点，将其加入到 Treap 的当前位置。
「节点的删除」同样是一个递归的过程，不过需要讨论多种情况：
如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子。
如果插入值等于当前节点值：
若当前节点数值的出现次数大于 1 ，则减一;
若当前节点数值的出现次数等于于 1 :
若当前节点没有左儿子与右儿子，则直接删除该节点（置 0）；
若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点；
若当前节点有左儿子与右儿子，则不断旋转 当前节点，并走到当前节点新的对应位置，直到没有左儿子或右儿子为止。
时间复杂度均为 O(log2n) 。
具体实现代码如下：
void ins(int &p,int x)
{
if (p==)
{
p=++sz;
tr[p].siz=tr[p].ct=,tr[p].val=x,tr[p].rnd=rand();
return;
}
tr[p].siz++;
if (tr[p].val==x) tr[p].ct++;
else if (x>tr[p].val)
{
ins(tr[p].r,x);
if (tr[rs].rnd<tr[p].rnd) lturn(p);
}else
{
ins(tr[p].l,x);
if (tr[ls].rnd<tr[p].rnd) rturn(p);
}
}
void del(int &p,int x)
{
if (p==) return;
if (tr[p].val==x)
{
if (tr[p].ct>) tr[p].ct--,tr[p].siz--;//如果有多个直接减一即可。
else
{
if (ls==||rs==) p=ls+rs;//单节点或者空的话直接儿子移上来或者删去即可。
else if (tr[ls].rnd<tr[rs].rnd) rturn(p),del(p,x);
else lturn(p),del(p,x);
}
}
else if (x>tr[p].val) tr[p].siz--,del(rs,x);
else tr[p].siz--,del(ls,x);
}
6.查询数x的排名
查询数x的排名可以利用在二叉搜索树上的相同方法实现。
具体思路为根据递归找到当前节点，并记录小于这个节点的节点的数量（左子树） 。
时间复杂度 O(log2n) 。
代码实现如下：
int find_pm(int p,int x)
{
if (p==) return ;
if (tr[p].val==x) return tr[ls].siz+;
if (x>tr[p].val) return tr[ls].siz+tr[p].ct+find_pm(rs,x);
else return find_pm(ls,x);
}
7.查询排名为x的数
查询排名为x的数可以利用在二叉搜索树上的相同方法实现。
具体思路为根据当前x来判断该数在左子树还是右子树 。
时间复杂度 O(log2n) 。
代码实现如下：
int find_hj(int p,int x)
{
if (p==) return inf;
if (tr[p].val<=x) return find_hj(rs,x);
else return min(tr[p].val,find_hj(ls,x));
}
8.查询数的前驱与后继
查询数的前驱与后继同样可以递归实现。查前驱即为递归当前数，走到小于等于x的节点，并记录其中最大的。后继同理。
时间复杂度 O(log2n) 。
代码实现如下：
int find_qq(int p,int x)
{
if (p==) return -inf;
if (tr[p].val<x) return max(tr[p].val,find_qq(rs,x));
else if (tr[p].val>=x) return find_qq(ls,x);
}
int find_hj(int p,int x)
{
if (p==) return inf;
if (tr[p].val<=x) return find_hj(rs,x);
else return min(tr[p].val,find_hj(ls,x));
}
下面放洛谷的模板题的代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int n,ans,tot,root;
struct Treap{
int val,l,r;
int id,size,cnt;
}t[maxn];
inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
}
inline void update(int k)
{t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].cnt;}
inline void left_rotate(int &k)
{
int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
t[y].size=t[k].size;update(k);k=y;
}
inline void right_rotate(int &k)
{
int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
t[y].size=t[k].size;update(k);k=y;
}
inline void ins(int &k,int x)
{
if(k==){
++tot;k=tot;t[k].val=x;
t[k].size=t[k].cnt=;
t[k].id=rand();return;
}
++t[k].size;
if(t[k].val==x)++t[k].cnt;
else if(x>t[k].val){
ins(t[k].r,x);
if(t[t[k].r].id<t[k].id)
left_rotate(k);
}
else{
ins(t[k].l,x);
if(t[t[k].l].id<t[k].id)
right_rotate(k);
}
}
inline void del(int &k,int x)
{
if(k==)return;
if(t[k].val==x){
if(t[k].cnt>){
--t[k].cnt;--t[k].size;
return;}
if(t[k].l*t[k].r==)
k=t[k].l+t[k].r;
else if(t[t[k].l].id<t[t[k].r].id)
right_rotate(k),del(k,x);
else left_rotate(k),del(k,x);
}
else if(x>t[k].val)
--t[k].size,del(t[k].r,x);
else --t[k].size,del(t[k].l,x);
}
inline int fid(int k,int x)
{
if(k==)return ;
if(t[k].val==x)return t[t[k].l].size+;
else if(x>t[k].val)
return t[t[k].l].size+t[k].cnt+fid(t[k].r,x);
else return fid(t[k].l,x);
}
inline int fin(int k,int x)
{
if(k==)return ;
if(x<=t[t[k].l].size)
return fin(t[k].l,x);
else if(x>t[t[k].l].size+t[k].cnt)
return fin(t[k].r,x-t[t[k].l].size-t[k].cnt);
else return t[k].val;
}
inline void pred(int k,int x)
{
if(k==)return;
if(t[k].val<x){
ans=k;pred(t[k].r,x);
}
else pred(t[k].l,x);
}
inline void sucd(int k,int x)
{
if(k==)return;
if(t[k].val>x){
ans=k;sucd(t[k].l,x);
}
else sucd(t[k].r,x);
}
int main()
{
n=read();
for(int i=;i<=n;i++){
int caozuo=read();
int x=read();ans=;
switch(caozuo){
case :ins(root,x);break;
case :del(root,x);break;
case :printf("%d\n",fid(root,x));break;
case :printf("%d\n",fin(root,x));break;
case :{pred(root,x);printf("%d\n",t[ans].val);break;}
case :{sucd(root,x);printf("%d\n",t[ans].val);break;}
}
}
return ;
}