这次我们来讲一讲Treap(splay以后再更)
平衡树是一种排序二叉树(或二叉搜索树)，所以排序二叉树可以迅速地判断两个值的大小，当然操作肯定不止那么多(不然我们还学什么)。
而平衡树在排序二叉树的基础上主要是增加了一个优化：就是高度较为平衡，并可以动态平衡。
而今天要讲的treap就是一种动态平衡的方法。
首先说声抱歉，因为没有那么多的时间，所以无法把左旋和右旋两种操作具体的讲，但是可以看刘汝佳的蓝书，讲得还是挺清楚的。
现在开始。
treap用的是一种比较玄学的方法，就是将每一个点还附上一个随机值，然后按照堆的性质，不管大小根堆都是一样的，所以我们每加入一个值，就利用上浮操作进行旋转，保持堆的性质，且不改变排序二叉树的性质。
操作很好理解，就是每次insert时进行判断就行了，若不满足，则上浮。
具体的排序二叉树的操作，我就不再赘述了，如果要学，可以看刘汝佳的蓝书(感觉在跟刘汝佳打广告)。
下面送上代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
int n,root,size,ans;
struct P{
int l,r,sz,key,rd,re;//re为重复次数，key为加入权值
}t[];
void update(int k)
{
t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].re;
}
void left(int &k)//右旋
{
int y=t[k].r;
t[k].r=t[y].l;
t[y].l=k;
t[y].sz=t[k].sz;
update(k);
k=y;
}
void right(int &k)//左旋
{
int y=t[k].l;
t[k].l=t[y].r;
t[y].r=k;
t[y].sz=t[k].sz;
update(k);
k=y;
}
void init(int &k,int x)//加入操作
{
if(k==)
{
size++;
k=size;
t[k].sz=;
t[k].re=;
t[k].key=x;
t[k].rd=rand();
return;
}
t[k].sz++;
if(t[k].key==x) t[k].re++;
else{
if(x>t[k].key)
{
init(t[k].r,x);
if(t[t[k].r].rd<t[k].rd) left(k);//这里和下面都是判断是不是满足堆的性质
}
if(x<t[k].key)
{
init(t[k].l,x);
if(t[t[k].l].rd<t[k].rd) right(k);
}
}
}
void del(int &k,int x)
{
if(k==) return;
if(t[k].key==x)
{
if(t[k].re>)
{
t[k].re--;
t[k].sz--;
return;
}
if(t[k].l*t[k].r==) k=t[k].l+t[k].r;//k代表指针的移动，所以移动到了左或右儿子
else
{
if(t[t[k].l].rd<t[t[k].r].rd){
right(k);
del(k,x);
}
else{
left(k);
del(k,x);
}
}
}
else{
if(x>t[k].key)
{
t[k].sz--;
del(t[k].r,x);
}
else{
t[k].sz--;
del(t[k].l,x);
}
}
}
int rank1(int k,int x)//找x的排名
{
if(k==) return ;
if(t[k].key==x) return t[t[k].l].sz+;
if(x>t[k].key) return t[t[k].l].sz+rank1(t[k].r,x)+t[k].re;
if(x<=t[k].key) return rank1(t[k].l,x);
}
int rank2(int k,int x)//找排名为x的数
{
if(k==) return ;
else if(x<=t[t[k].l].sz) return rank2(t[k].l,x);
else if(x>t[t[k].l].sz+t[k].re) return rank2(t[k].r,x-t[t[k].l].sz-t[k].re);
else return t[k].key;
}
void pre(int k,int x)//找前驱
{
if(k==) return;
if(t[k].key<x)
{
ans=k;
pre(t[k].r,x);
}
else pre(t[k].l,x);
}
void nxt(int k,int x)//找后继
{
if(k==) return;
if(t[k].key>x)
{
ans=k;
nxt(t[k].l,x);
}
else nxt(t[k].r,x);
}
int main()
{
srand(time());
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int num,x;
scanf("%d%d",&num,&x);
if(num==) init(root,x);
if(num==) del(root,x);
if(num==) printf("%d\n",rank1(root,x));
if(num==) printf("%d\n",rank2(root,x));
if(num==)
{
pre(root,x);
printf("%d\n",t[ans].key);
}
if(num==)
{
nxt(root,x);
printf("%d\n",t[ans].key);
}
}
return ;
}
模板题：https://www.luogu.org/problemnew/show/P3369
谢谢大家的观看。
如有不妥之处，请大家指出。