学完fhq treap后决定发篇总结
我学习的是这篇题解，代码也是模仿这位大佬的

备注:文本可能有一些看不懂的地方，可以仔细看代码模拟，非常有助于理解

treap是一种平衡树，既满足二叉搜索树的性质，也满足小根堆的性质

treap上每个节点有val值和key值。

val值是我们需要的权值，在treap上val值满足二叉搜索树的性质，也就是每个节点的val值大于其左子树中所有节点的val值，小于其右子树中所有节点的val值。

key值是我们用rand()随机给的，在treap上key值满足小根堆的性质，也就是每个节点的key值小于其子树中所有节点的key值。

接下来着重介绍一下treap的两个基本操作:merge和split,借助这两个操作可以达到一般平衡树能达到的所有功能

1.split

这个函数的功能是把一个treap按权值分成两个，有两种形式，一种按权值k划分，一种按权值排名k划分

1.权值版

void split(int now,int k,int &x,int &y){
	if(!now)x=y=0;
	else {
		if(val[now]<=k)
			x=now,split(ch[now][1],k,ch[now][1],y);
		else 
			y=now,split(ch[now][0],k,x,ch[now][0]);
		update(now);
	}
}

x,y是指向左右两颗新树的下一个儿子，如果该节点的val<=k，把该点连同左子树接到左新树上，继续split右子树，否则反之。以val<=k为例，因为右子树中所有节点val值都比该节点大，所有我们可以把以后val<=k的节点放心的接到x的右子树上，也就是把x指向ch[now][1]

2.k大版

void split_kth(int now,int k,int &x,int &y){
	if(!now)x=y=0;
	else {
		if(k>sz[ch[now][0]])
			x=now,split_kth(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);
		else
			y=now,split_kth(ch[now][0],k,x,ch[now][0]);
		update(now);
	}
}

有点类似找第k大，其他的部分与权值版类似

2.merge

这个函数的功能是把两个treap合并，且前一个treap中所有点的权值小于后一个

int merge(int x,int y){
	if(!x||!y)return x|y;
	if(key[x]<key[y]){
		ch[x][1]=merge(ch[x][1],y);
		update(x);
		return x;
	}
	else {
		ch[y][0]=merge(x,ch[y][0]);
		update(y);
		return y;
	}
}

因为比较简单就不做解释了，可以看上述大佬的题解

代码

下面是洛谷P3369普通平衡树的代码，给出了treap的常见函数

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int M=1e5+5,P=1e9+7,base=269;
inline int rd(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,ch[M][2],val[M],sz[M],key[M],tot,rt;
inline int Rand(){return 1ll*rand()*rand()%P;}
inline void update(int p){sz[p]=1+sz[ch[p][0]]+sz[ch[p][1]];}
int new_node(int v){
	sz[++tot]=1;
	key[tot]=Rand();
	val[tot]=v;
	return tot;
}
void split(int now,int k,int &x,int &y){
	if(!now)x=y=0;
	else {
		if(val[now]<=k)
			x=now,split(ch[now][1],k,ch[now][1],y);
		else 
			y=now,split(ch[now][0],k,x,ch[now][0]);
		update(now);
	}
}
void split_kth(int now,int k,int &x,int &y){
	if(!now)x=y=0;
	else {
		if(k>sz[ch[now][0]])
			x=now,split_kth(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);
		else
			y=now,split_kth(ch[now][0],k,x,ch[now][0]);
		update(now);
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	if(key[x]<key[y]){
		ch[x][1]=merge(ch[x][1],y);
		update(x);
		return x;
	}
	else {
		ch[y][0]=merge(x,ch[y][0]);
		update(y);
		return y;
	}
}
void insert(int &p,int v){
	int x=0,y=0;
	split(p,v,x,y);
	p=merge(merge(x,new_node(v)),y);
}
void del(int &p,int v){
	int x=0,y=0,z=0;
	split(p,v,x,y);
	split_kth(x,sz[x]-1,x,z);
	p=merge(x,y);
}
int rank(int p,int v){
	int x=0,y=0,res;
	split(p,v-1,x,y);
	res=sz[x]+1;
	p=merge(x,y);
	return res; 
}
int kth(int p,int k){
	while(1){
		if(k<=sz[ch[p][0]])p=ch[p][0];
		else if(k==sz[ch[p][0]]+1)return p;
		else k-=sz[ch[p][0]]+1,p=ch[p][1];
	}
}
int pre(int &p,int v){
	int x=0,y=0,res;
	split(p,v-1,x,y);
	res=kth(x,sz[x]);
	p=merge(x,y);
	return res;
}
int nxt(int &p,int v){
	int x=0,y=0,res;
	split(p,v,x,y);
	res=kth(y,1);
	p=merge(x,y);
	return res;
}
int main(){
	srand(time(0));
	int op,x;
	n=rd();
	for(int i=1;i<=n;++i){
		op=rd(),x=rd();
		if(op==1)insert(rt,x);
		if(op==2)del(rt,x);
		if(op==3)printf("%d\n",rank(rt,x));
		if(op==4)printf("%d\n",val[kth(rt,x)]);
		if(op==5)printf("%d\n",val[pre(rt,x)]);
		if(op==6)printf("%d\n",val[nxt(rt,x)]);
	}

	return 0;
}