标签：get int t2 t1 treap merge id 二叉 fhp

问题背景：

你需要维护一个整数集合，可以满足一下几种操作：

插入一个整数 xx。
删除一个整数 xx（若有多个相同的数，只删除一个）。
查询整数 xx 的排名（排名定义为比当前数小的数的个数 +1+1）。
查询排名为 xx 的数（如果不存在，则认为是排名小于 xx 的最大数。保证 xx 不会超过当前数据结构中数的总数）。
求 xx 的前驱（前驱定义为小于 xx，且最大的数）。
求 xx 的后继（后继定义为大于 xx，且最小的数）。

这时候其实有很多种办法：权值线段树， set 等都可以维护。

我们选择用 fhp-treap 来做

算法目的

我们都知道二叉排序树可能会退化为$O(n)$，是因为当他的结构为链的时候深度超级大

我们想办法让他的深度最多只有$O(logn)$，这样我们就可以用$O(logn)$的时间内进行操作

现在我们就弄了一个东西叫做树堆

treap=tree+heap

实现方式

大致思想

给每个东西随机化一下，让他既满足排序树的性质，又满足堆的性质，用随机来优化深度

我们定义两个操作：treap的合并与让treap<=x的部分分离

具体实现

首先考虑我们有这两个操作怎么样能够满足上面那六种情况

1. 插入某一个数x：ins(x)

我们把小于等于x的子树从大树中分离，得到左边的是t1，右边的是t2

接着，我们把插入的这个点定为x，合并t1和x，再合并前面的和t2

2. 删除一个数x：del(x)

把$≤x-1$的树分离，得到左边的t1和右边的t2，然后再把t2中$≤x$的树分离，得到t3（全为x）和t2。
因为删除的数可能有很多个，我们只能删一个，我们就考虑删除t3的堆顶，即把t3的左子树t4和t3的右子树t5独立开来，把t1和t4合并，t5和t2合并，最后两个再同时合并，就可以得到一个没有t3（此时只有一个x）的treap了

3. 查找x的排名：get_rank(x);

首先我们需要把$≤x-1$的子树分离出来，在查询他们的节点个数，然后合并就行了。
最后答案就是节点个数+1

tips：由于需要记录节点个数，因此还需要有一个sum和push_up

4. 查找排名为x的值：get_data(fx,x);

从树顶开始遍历即可，由大小决定走左边还是右边或者现在就返回
与线段树二分类似

5. 找x的前驱 get_pri(x);

把$≤x-1$的子树get_data他的大小（能找到他最右边的）

6. 找x的后继 get_suf(x);

把>x的子树get_data(1)（能找到他最左边的）

我们就能够知道，结构体需要定义的东西和push_up：

struct node {
	int val;//键值
	int pri;//优先级，即开始会给他一个rand让他随机调整
	int sum;//子树大小
	int ls,rs;//左儿子右儿子
}d[N];
//......
void push_up(int id) {
	d[id].sum=d[d[id].ls].sum+d[d[id].rs].sum+1;//加一不能忘
}

然后考虑怎样写split和merge

1. split

因为现在优先级是正确的，上面的优先级一定比现在的大，只要符合是上面的连向下面的就符合优先级的性质了，那么只需要考虑值的大小分裂

如果id=0，即已经分完了，返回
如果此时 $ id->val ≤x $ id和左边的一定都在左子树里面，此时只需分裂右子树，左子树的根l=id，l的右子树 和 r 递归找
如果此时 $ id->val >x $ id和右边的一定都在右子树里面，此时只需分裂左子树，右子树的根r=id，l 和 r的左子树 递归找

左子树不断地想填右边，右子树不断地想填左边

void split(int id,int x,int &l,int &r){
	//l,r引用的是两个子树的根
	if(id==0) {
		l=0;r=0;return ;
	}
	if(d[id].val<=x) {
		l=id;
		split(d[id].rs,x,d[id].rs,r);
		//顺序千万不能搞反，否则你调大半天不知道啥问题
	} else {
		r=id;
		split(d[id].ls,x,l,d[id].ls);
	}
	push_up(id);
	//一定要记得跟新他的sum，
	//为什么只需要更新一个呢，因为另一个在下一层递归中已经被更新了
}

2. merge（与split对称不知这样表述对不对）

因为现在l值一定小于r值是正确的，只要不改变对于两棵树树内部的相对大小关系（即合并完原来的左边的一定在右边的，那我们就只需要考虑优先级了

如果id=0，即已经分完了，返回
同理，谁的优先级小（小根堆）那就谁做老大，并相应的保留左子树和右子树（值就能不受改动），在递归他未确定的部分和另一棵子树

左子树不断地保留左边，右子树不断地保留右边//因为左边右边分别比上面的小和大

int merge(int l,int r) {
	if(!l||!r) return l+r;
	if(d[l].pri<d[r].pri) {
		d[l].rs=merge(d[l].rs,r);//注意顺序
		push_up(l);
		return l;
	} else {
		d[r].ls=merge(l,d[r].ls);//注意顺序，最好画个图推一下
		push_up(r);
		return r;
	}
}

然后通过整理，我们就能够造出这样一种数据结构满足上述要求了：

代码实现细节：

void ins(int x) {
	int t1=0,t2=0,t=0;//注意初值
	d[++cnt].val=x;
	d[cnt].sum=1;
	d[cnt].pri=rand();
	t=cnt;
	split(fx,x,t1,t2);//注意顺序
	fx=merge(merge(t1,t),t2);//每次合并一定要记录新的根
}

void del(int x) {
	int t1=0,t2=0,t3=0,t4=0,t5=0;//t3 will be deleted
	split(fx,x-1,t1,t2);
	split(t2,x,t3,t2);
	t4=d[t3].ls;t5=d[t3].rs;
	fx=merge(merge(t1,t4),merge(t5,t2));
	d[t3].val=-1;
}

int get_rank(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x-1,t1,t2);
	ans=d[t1].sum+1;
	fx=merge(t1,t2);
	return ans;
}

int get_data(int num,int x) {
	if(d[d[num].ls].sum+1==x) return d[num].val;
	if(d[d[num].ls].sum>=x) return get_data(d[num].ls,x);
	else return get_data(d[num].rs,x-d[d[num].ls].sum-1);
}

int get_pri(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x-1,t1,t2);
	ans=get_data(t1,d[t1].sum);
	fx=merge(t1,t2);
	return ans;
}

int get_suf(int x) {
	int t1=0,t2=0,ans=0;
	split(fx,x,t1,t2);
	ans=get_data(t2,1);
	fx=merge(t1,t2);
	return ans;
}

这样，我们就完成了这种数据结构

标签：get,int,t2,t1,treap,merge,id,二叉,fhp
From： https://www.cnblogs.com/olerdada/p/17048226.html

学习笔记：二叉平衡树之 fhp-treap