fhq treap 学习笔记

前言

这是一个在很久很久以前学了的知识点

当时是一坨平衡树一起学的，学了替罪羊，fhq，splay

然后当时听说 splay 更牛逼，而且维护 LCT 需要 splay，就不管其他两个平衡树了，然后就忘了怎么写 fhq 了（雾）

后面发现 splay 这个东西又臭又长，写起来要调一年

加上同机房的人疯狂安利 fhq treap，就来学了一下

发现是真的简单，好写，好用（真香）

正片

对于一个点，你需要用于维护平衡树的基本信息有 ch[2],size,val,rnd 其他的根据题目再定

其中 ch[0/1] 是左右儿子，size 是子树大小，rnd 是一个随机的值

split

核心操作之一

有两种 split，第一种是根据权值 split，第二种是根据 rank split

大同小异，给出第一种的详细说明

void split(int node,int val,int &x,int &y)

表示把 \(node\) 的子树分成 \(\leq val\) 和 \(> val\) 两部分，分别存入 \(x,y\)

核心思想是根据 \(node\) 的节点状态分开

给出实现

void split(int node,int val,int &x,int &y)
{
	if (!node) return x=y=0,void();
	if (t[node].val<=val)
	{
		x=node;
		split(t[node].ch[1],val,t[x].ch[1],y);
	}
	else
	{
		y=node;
		split(t[node].ch[0],val,x,t[node].ch[0]);
	}
	push_up(node); 
}

merge

核心操作之二

int merge(int x,int y)

用于把 \(x,y\) 的子树合并成一棵数，并返回节点值

注意这里要保证 \(y\) 中所有的节点按照 cmp 都严格不小于 \(x\) 中所有的节点

实现过程中用了随机的性质，所以生成的树高期望是 \(O (\log n)\) 的

给出实现

int merge(int x,int y)
{
	if (!x||!y) return x+y;
	if (t[x].rnd