【学习笔记】fhq_treap 无旋平衡树

推一个视频

引入

Treap平衡树原型：基于旋转实现的BST+Heap，通过随机索引和堆使得BST的单次复杂度稳定在 \(O(\log n)\)。

fhq treap则是将treap改造了一下，变成了基于分裂与合并实现的码量小但常数稍大的平衡树。

根据按值分裂与按大小分裂可以实现普通平衡树与文艺平衡树的功能（以及可持久化）。

详解

在fhq_treap中我们用一棵树的根来代表这棵树，一会你就能理解了。

前置代码：

struct node{
	int lc,rc,siz,pri,val;
}t[N+5];
int cnt,root;
mt19937 rnd(233);
inline int newcode(int val){
	t[++cnt].val=val;
	t[cnt].lc=t[cnt].rc=0;
	t[cnt].siz=1;
	t[cnt].pri=rnd();
	return cnt;
}
inline void upt(int now){t[now].siz=1+t[t[now].lc].siz+t[t[now].rc].siz;}

先来解决两个fhq_treap的基本操作：

1.Split（分裂）

按key这个值分裂的步骤即是，将小于等于key的数作为一棵新树X树，大于的则作为新树Y树。下图为一个样例：

由于BST的性质，当前节点的val小于等于key时可以直接把该节点加入X树，且无需再考虑该节点的左子树（因为左子树上的值都将小于等于当前节点的值），val大于key时同理。但另一个子树上就有可能出现大于key的或小于等于的，因此我们需要递归考虑左/右子树，并将当前节点的左/右儿子作为指针，匹配新的X/Y树成员（如样例中40的左儿子更新为30）

void split(int now,int val,int &x,int &y){
	if(!now){                  //空节点
		x=y=0;
		return;
	} 
	if(t[now].val<=val){
		x=now;             //加入x树
		split(t[now].rc,val,t[now].rc,y);   //递归考虑右子树
	}else{
		y=now;
		split(t[now].lc,val,x,t[now].lc);   //同理
	}
	upt(now);                  //更新siz
}

这里的 x 与 y 可以这么理解：
当我们还未在X树中加入任何数时，x引用的是X树的根节点编号，y同理；
当树中已存在数后，这里引用的便是已加入节点的左儿子/右儿子，用于匹配下一个将加入的节点

2.Merge（合并）