无需旋转のFHQ-treap！

update：2023.1.12 以前写的博客看起来太仓促了，修改了一下。
update：2023.6.21 还是只会写模板的我来再修一下（其实是基本重写了一遍）。
第一次写是2022.8.9，现在一看都快隔着一年了，令人感慨。

FHQ-Treap

学习这种平衡树不需要了解 treap，据说 treap 和 splay 能干的事情他也能干，而且还支持可持久化。

FHQ-Treap 虽然名字里带 treap，但是我感觉和 treap 没有多大的关系，主要是因为 FHQ 不需要 treap 的核心操作——旋转。

而 FHQ 为了保持一个平衡的状态，通过两个基本的操作来实现其他各种操作。

前置知识

二叉搜索树

一棵满足以下条件的二叉树：左子树的点的值都小于根节点的值，右子树的点的值都大于根节点的值，且左右子树都满足这个性质。

堆

一种维护数据让其最值在最上方的数据结构，比如大根堆就是大的值在上面，小的值在下面。

原理

FHQ-Treap 不是通过旋转来保持平衡的，而是通过两个函数 split 和 merge 。顾名思义，split 就是分裂，merge 就是合并。当然，从最底层的原理来看，还不是这两个函数。FHQ-Treap 中的 Treap 代表 Tree + Heap，也就是说，FHQ-Treap 会按二叉搜索树一样根据键值排序结点，并且随机赋给每个结点一个优先级，按照二叉堆的顺序排序结点（这里用大根堆）。Treap 通过旋转，使平衡树同时满足这两个性质，从而达到平衡。而FHQ-Treap 通过调用 merge 函数时使平衡树满足堆序，实现原理与 Treap 不同，这也是为什么我上面说不用了解 Treap 的原因。

变量与函数

先看一下定义的数组：

int ch[N][2], val[N], siz[N], key[N], cnt;
int T, rt = 0;

inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}

inline int node(int x)
{
	cnt++;
	siz[cnt] = 1;
	val[cnt] = x;
	key[cnt] = rand();
	return cnt;
}

其中 ch 表示当前结点的左右儿子的编号，\(0\) 是左儿子，\(1\) 是右儿子。

val 是结点存储的值，siz 是以当前点为根的子树大小，key 是我们赋的随机权值。

push_up 主要是用于更新 siz ，因为在 FHQ 中查找有关排名之类的操作都是需要用到 siz 来判断的，所以主要是更新子树的大小。

node 函数的含义就是新开一个点，里面的 key 要赋随机权值，在初始化完之后要返回当前点的编号。

分裂与合并

按值分裂

我们先来看一下代码：

inline void split(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

函数里面的参数，x 是当前点的编号，k 是分裂的权值，也就是我们现在是把小于等于 k 的结点分为一棵子树，大于 k 的结点分为一棵子树；xx,yy 是我们分裂出来的两棵树的根结点。

根据二叉搜索树的性质，我们首先是判断当前点的值是不是小于等于 k ，如果成立则把当前 xx 替换成 x ，也就是当前结点，表示当前结点被划分到左边的子树中，然后在往下递归，因为当前点的左子树的值肯定小于等于 x 的权值，所以也成立，在左子树，而右子树的不一定会成立，所以我们去判断右子树。

如果要是当前点的值大于 k 的话，我们就直接把他给分给右子树，也就是把 yy 替换成 x ，然后继续递归。

我们重复上面的步骤，如果当前点是空的就直接返回不属于任何一个结点的子节点，也就是在递归回去的过程中把分裂完后子节点为空的结点的 ch 给更新掉。

图片来自OI—Wiki。

按排名分裂

其实和上面的是差不多的，就是把值改成了排名，在判断的时候用的是 siz。

inline void split2(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - size[ch[x][0]] - 1, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

要注意在当前点被分到 xx 的时候，我们需要将 k 减去 siz[x] + 1 ，因为我们在往下是到右子树去找，所以之前左子树占掉的排名个数要减去。

合并

先来看代码：

inline 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);
		push_up(x);
		return x;
	}
	else 
	{
		ch[y][0] = merge(x, ch[y][0]);
		push_up(y);
		return y;
	}
}

我们在合并的时候，就要考虑来满足堆的性质了，让随机权值最大的点在上面。

因为两个分裂出来的子树已经有序，所以我们在合并的时候只需要考虑把哪个树「放在上面」，把哪个「放在下面」，也就是是需要判断将哪个一个树作为子树。显然，根据堆的性质，我们需要把 key 值大的放在上面（上面说过里默认用大根堆）

同时，我们还需要满足搜索树的性质，所以若 xx 的根结点的 key 小于 yy 的，那么 xx 即为新根结点，并且 yy 因为 val 值比 xx 更大，应与 xx 的右子树合并；反之，则 yy 作为新根结点，然后因为 xx 的 val 值比 yy 小，与 yy 的左子树合并。

其他操作

插入点

split(rt, a, x, y);
rt = merge(merge(x, node(a)), y);

我们把当前的整棵树按照给定的点的权值给分开，然后新开一个点，将其与 x 合并后再与 y 合并即可。

删除点

split(rt, a, x, z);
split(x, a - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
rt = merge(merge(x, y), z);

我们把小于等于 a 的点给分出来，然后从这棵子树里面把小于等于 a-1 的点给分出来，也就是我们相当于 y 中的结点全是等于 a 的，然后我们把左右儿子合并就把一个值为 a 的点给删掉了，然后合并起来即可。

查询给定值的排名

split(rt, a - 1, x, y);
cout << siz[x] + 1 << endl;
rt = merge(x, y);

我们先把小于等于 a-1，也就是小于 a 的值都给分出来，然后以他为根的子树大小就是当前 a 值的排名了。

查询给定排名的值

inline int get_rank(int x, int k)
{
	while(1)
	{
		if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}
		if(k == siz[ch[x][0]] + 1) return x;
		else k -= siz[ch[x][0]] + 1, x = ch[x][1];
	}
}

这个没有什么好方法，只能暴力找，但由于我们平衡树的优良结构，复杂度是 \(O(\log n)\) 的。

查询前驱

split(rt, a - 1, x, y);
cout << val[get_rank(x, siz[x])] << endl;
rt = merge(x, y);

我们把小于等于 a-1 的点也就是小于 a 的点给分出来然后直接查询我们的 x 中最后一个点的序号然后输出对应值即可。

查询后继

split(rt, a, x, y);
cout << val[get_rank(y, 1)] << endl;
rt = merge(x, y);

跟上面的原理差不多，我们只不过是在大于 a 的结点的子树中找了第一个大于 a 的点。

P3369【模板】普通平衡树

#include <bits/stdc++.h>

#define int long long
#define N 500100

using namespace std;

int ch[N][2], val[N], siz[N], key[N], cnt;
int T, rt = 0;

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

inline void push_up(int x) {siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];}

inline int node(int x)
{
	cnt++;
	siz[cnt] = 1;
	val[cnt] = x;
	key[cnt] = rand();
	return cnt;
}

inline 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);
		push_up(x);
		return x;
	}
	else 
	{
		ch[y][0] = merge(x, ch[y][0]);
		push_up(y);
		return y;
	}
}

inline void split(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(val[x] <= k) xx = x, split(ch[x][1], k, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

inline void split2(int x, int k, int &xx, int &yy)
{
	if(! x) return xx = yy = 0, void();
	if(siz[ch[x][0]] + 1 <= k) xx = x, split(ch[x][1], k - siz[ch[x][0]] - 1, ch[x][1], yy);
	else yy = x, split(ch[x][0], k, xx, ch[x][0]);
	push_up(x);
	return ;
}

inline int get_rank(int x, int k)
{
	while(1)
	{
		if(k <= siz[ch[x][0]]) {x = ch[x][0]; continue;}
		if(k == siz[ch[x][0]] + 1) return x;
		else k -= siz[ch[x][0]] + 1, x = ch[x][1];
	}
}

signed main()
{
	srand((unsigned)time(NULL));
	T = read();
	while(T --)
	{
		int op = read(), a = read(), x, y, z;
		if(op == 1)
		{
			split(rt, a, x, y);
			rt = merge(merge(x, node(a)), y);
		}
		if(op == 2)
		{
			
			split(rt, a, x, z);
			split(x, a - 1, x, y);
			y = merge(ch[y][0], ch[y][1]);
			rt = merge(merge(x, y), z);
		}
		if(op == 3)
		{
			split(rt, a - 1, x, y);
			cout << siz[x] + 1 << endl;
			rt = merge(x, y);
		}
		if(op == 4) cout << val[get_rank(rt, a)] << endl;
		if(op == 5)
		{
			split(rt, a - 1, x, y);
			cout << val[get_rank(x, siz[x])] << endl;
			rt = merge(x, y);
		}
		if(op == 6)
		{
			split(rt, a, x, y);
			cout << val[get_rank(y, 1)] << endl;
			rt = merge(x, y);
		}
	}
	return 0;
}