FHQ-treap学习笔记

平衡树，即平衡二叉搜索树。
二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。（from 百度百科）
而在使用这种数据结果时，如果题目数据是顺序的，那么这棵BST将被卡成一条链，复杂度就假了。
于是就出现了平衡二叉搜索树，这种树可以在维持BST的性质的同时，通过各种手段，保证树高在log级。
今天，我将介绍的是FHQ-treap
FHQ-treap每个点除了维护原本的key值，还维护一个在节点新加入时随机生成的val值
要求要保证key值满足BST的性质，val值满足小根堆（大根堆）的性质。
FHQ-treap由两个主要操作，split和merge
如下：

1.split

split可以将一颗FHQ-treap分裂为两棵FHQ-trea，我们成为左树和右树，其中左树的key值<=x，右树的key值>x（x为split传入的参数）

void split(int pos,int x,int &l,int &r){//pos表示当前便利到的节点，l，r表示当前左树、右树的根。
	if(!pos){//如果当前遍历到的节点为0，那么为空子树，左右子树根都是0
		l=r=0;
		return ;
	}
	if(tr[pos].key<=x){//如果当前节点key值<=x，那么它及它的左子树都应当被分为左树
		l=pos;
		split(tr[l].rs,x,tr[l].rs,r);
	}else{//反之，同上
		r=pos;
		split(tr[r].ls,x,l,tr[r].ls);
	}
	push_up(pos);//由于树的结构改变，记得push_up
}

2.merge

merge可以将两棵值域无交集的FHQ-treap合并

int merge(int l,int r){//两颗treap的根，返回合并后的根
	if(l==0 || r==0)return l+r;//如果其中由一颗空子树，那么返回另一个；如果都是就返回0
	if(tr[l].val<=tr[r].val){//如果l的val<=r的val，那么将r并入l（为了满足小根堆的性质）
		tr[l].rs=merge(tr[l].rs,r);
		push_up(l);//同理，不要忘记push_up
		return l;
	}else{//同上
		tr[r].ls=merge(l,tr[r].ls);
		push_up(r);
		return r;
	}
}

完成了split和merge操作，其他各种平衡树上得操作就很简单了。
便可以完成普通平衡树

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int n;
struct tree{
	int sz,val,key,ls,rs;
}tr[200005];
int rt=0,tot=0;
int get(int x){
	tr[++tot].sz=1;
	tr[tot].val=rnd();
	tr[tot].key=x;
	return tot;
}
void push_up(int pos){
	tr[pos].sz=tr[tr[pos].ls].sz+tr[tr[pos].rs].sz+1;
}
void split(int pos,int x,int &l,int &r){
//	printf("%d %d %d %d\n",pos,x,l,r);
	if(!pos){
		l=r=0;
		return ;
	}
	if(tr[pos].key<=x){
		l=pos;
		split(tr[l].rs,x,tr[l].rs,r);
	}else{
		r=pos;
		split(tr[r].ls,x,l,tr[r].ls);
	}
	push_up(pos);
}
int merge(int l,int r){
	if(l==0 || r==0)return l+r;
	if(tr[l].val<=tr[r].val){
		tr[l].rs=merge(tr[l].rs,r);
		push_up(l);
		return l;
	}else{
		tr[r].ls=merge(l,tr[r].ls);
		push_up(r);
		return r;
	}
}
void insert(int x){
	int p=0,q=0;
	split(rt,x-1,p,q);
	rt=merge(merge(p,get(x)),q);
}
void del(int x){
	int p=0,q=0,r=0;
	split(rt,x-1,p,q);split(q,x,q,r);
	q=merge(tr[q].ls,tr[q].rs);
	rt=merge(merge(p,q),r);
}
int get_rk(int x){
	int p=0,q=0,res=0;
	split(rt,x-1,p,q);
	res=tr[p].sz+1;
	rt=merge(p,q);
	return res;
}
int get_num(int pos,int x){
	int u=tr[tr[pos].ls].sz;
	if(x==u+1)return tr[pos].key;
	else if(x<=u)return get_num(tr[pos].ls,x);
	else return get_num(tr[pos].rs,x-u-1);
}
int pre(int x){
	int p=0,q=0,res=0;
	split(rt,x-1,p,q);
//	printf("%d %d\n",p,tr[p].sz);
	res=get_num(p,tr[p].sz);
	rt=merge(p,q);
	return res;
}
int suf(int x){
	int p=0,q=0,res=0;
	split(rt,x,p,q);
	res=get_num(q,1);
	rt=merge(p,q);
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int op,x;scanf("%d%d",&op,&x);
		if(op==1)insert(x);
		else if(op==2)del(x);
		else if(op==3)printf("%d\n",get_rk(x));
		else if(op==4)printf("%d\n",get_num(rt,x));
		else if(op==5)printf("%d\n",pre(x));
		else printf("%d\n",suf(x));
	}
	return 0;
}

请注意区分val和key的区别