FHQ-Treap

\(FHQ-Treap\) 是无旋平衡树的一种，码量相对少，并且简单易懂。

一下简称 \(treap\) （注意还有别的 \(treap\) ，但是在本文中仅指 \(FHQ-Treap\) )。

\(treap\) 仅需要合并和分裂。

\(treap\) 结合了小根堆（父亲节点权值比儿子小）和二叉查找树（左子树的值比根小，右子树的值比根大）的特性。

所以对于每个节点的值的大小，都满足左子树比他小，右子树比他大（或者一样大），而除了这个节点本身的值，我们还要给他赋一个随机权，作为小根堆的排名标准。

先来讲如何分裂。

定义结构体 \(bal\) ，\(t.a\)表示左孩子的节点编号，\(t.b\) 表示右孩子的节点编号，\(split\) 函数返回值类型为 \(bal\) ，参数是需要分裂的树的根的编号和需要按什么值 \(k\)分裂（即分裂后会返回两个根节点编号，一个树所有值小于 \(k\) ，另一个树所有值大于等于 \(k\) ），另外为了维护每个子树的大小，在分裂完之后一定要更新 \(siz\) 。

struct bal
{
	int a, b;
	bal(int aa = 0, int bb = 0)
	{
		a = aa; b = bb;
	}
};
void pushup(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1; }
bal split(int u, int x)
{
	if (!u) return bal(0, 0);
	if (key[u] < x)
	{
		bal t = split(son[u][1], x);
		son[u][1] = t.a;
		pushup(u);
		return bal(u, t.b);
	}
	else
	{
		bal t = split(son[u][0], x);
		son[u][0] = t.b;
		pushup(u);
		return bal(t.a, u);
	}
}

另外一个核心操作是 \(merge\) ，也就是分裂。函数返回值是合并后的根节点编号，参数是需要合并的两个子树的根节点的编号。对于这两个节点，一定是一个树上所有的值都小于另一个树上的值，不然无法同时维护随机权和值。如果第一个子树的随机权小于另一个（即更优先），将另一个子树和这个子树的右子树合并，否则反之。

int merge(int u, int v)
{
	if (!u || !v) return u + v;
	if (wei[u] < wei[v])
	{
		son[u][1] = merge(son[u][1], v);
		pushup(u);
		return u;
	}
	else
	{
		son[v][0] = merge(u, son[v][0]);
		pushup(v);
		return v;
	}
}

此外，以上两个操作都不要忘记判断边界情况。

接下来是插入某个值。

为了满足 \(merge\) 的两个子树的大小关系，我们不能将需要插入的值直接和原树合并，而是需要先把原树分裂成一个大于插入值，一个小于插入值，再依次合并，每次插入还要记得初始化。

void insert(int x)
{
	cnt ++; key[cnt] = x; wei[cnt] = rand1(), siz[cnt] = 1;
	bal t = split(root, x);
	root = merge(merge(t.a, cnt), t.b);
}

下面是删除某个数x。

我们希望有一个树的根的值是这个需要删除的值，然后直接合并他的左右儿子。我们还是考虑分裂，将原树分为 \(u\) 和 \(v\) 两个子树，其中 \(u\) 的所有值都小于 \(x\) ，\(v\) 中的所有值都大于等于 \(x\) ，但是此时我们不能直接删掉 \(v\) 的根节点，因为 \(v\) 的根节点不一定是 \(x\) ，所以还有一个办法：我们将 \(v\) 再分为两个子树，一个子树 \(a\) 的所有值都小于 \(x + 1\) ，另一个子树 \(b\) 的所有值都大于等于 \(x + 1\) ，这样子树 \(a\) 就只有值 \(x\) 了，放心删！

void erase(int x)
{
	bal wtz = split(root, x);
	bal gyx = split(wtz.b, x + 1);
	gyx.a = merge(son[gyx.a][0], son[gyx.a][1]);
	root = merge(wtz.a, merge(gyx.a, gyx.b));
}

接下来是根据值查找数 \(x\) 的排名。

这很简单，先把原树分为小于 \(x\) 的子树 \(u\) 和大于等于 \(x\) 的子树 \(v\)，数 \(x\) 的排名就是 \(u\) 的大小加上 \(1\) 。

int find1(int x)
{
	bal wtz = split(root, x);
	int res = siz[wtz.a] + 1;
	root = merge(wtz.a, wtz.b);
	return res;
}

再来是根据排名 \(k\) 找值。

首先当前位置 \(pos\) 为 \(root\) （原树的根节点），如果 \(root\) 的左子树个数大于等于 \(k\) 说明这个值在左子树中，\(pos\) 更新为左儿子。

否则如果 \(pos\) 的左子树大小为 \(k-1\) ，即 \(pos\) 刚好为排名 \(k\) 的元素，就返回这个值。

如果都不是，说明这个值在右子树中，将 $pos $赋为右儿子， \(k\) 减去右儿子加上根的大小。

int find2(int x)
{
	int pos = root;
	while (1)
	{
		if (siz[son[pos][0]] + 1 == x) return key[pos];
		if (siz[son[pos][0]] >= x) pos = son[pos][0];
		else x -= siz[son[pos][0]] + 1, pos = son[pos][1];
	}
}

下面两个操作是查询前驱和后继。

其实只要理解了按照排名找值和按照值找排名，这两个操作会变得非常简单。

前驱就是排名比这个数的排名小 \(1\) 的数，后继就是比这个值大 \(1\) 的数的排名（注意平衡树中不一定存在这个大 \(1\) 的数，但是比他大 \(1\) 的数如果排个名，那么这个数的名次就是后继在原树中的名次）。

这两个操作都是先按值找排名，再按这个排名去找值就行了。

int lst(int x) { return find2(find1(x) - 1); }
int nxt(int x) { return find2(find1(x + 1)); }

这里补充一下随机权（即按照这个权值维护小根堆）的用处。

所谓平衡树，就是让这个树的高度是平衡的，因为合并和分裂是递归式的，所以如果树高为 \(n\) ，时间绝对爆炸，所以我们要用随机权平衡树高。虽然笔者能力有限，不会证明，但是结论是这样做可以使树高的期望维持在 \(log n\) 左右，那么总的时间复杂度就是 \(nlogn\)。

下面是模板题总代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct bal
{
	int a, b;
	bal(int aa = 0, int bb = 0)
	{
		a = aa; b = bb;
	}
};
int key[N], wei[N], son[N][2], cnt, seed = 1, siz[N], root;
int rand1() { return seed *= 19260817; }
void pushup(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1; }
bal split(int u, int x)
{
	if (!u) return bal(0, 0);
	if (key[u] < x)
	{
		bal t = split(son[u][1], x);
		son[u][1] = t.a;
		pushup(u);
		return bal(u, t.b);
	}
	else
	{
		bal t = split(son[u][0], x);
		son[u][0] = t.b;
		pushup(u);
		return bal(t.a, u);
	}
}
int merge(int u, int v)
{
	if (!u || !v) return u + v;
	if (wei[u] < wei[v])
	{
		son[u][1] = merge(son[u][1], v);
		pushup(u);
		return u;
	}
	else
	{
		son[v][0] = merge(u, son[v][0]);
		pushup(v);
		return v;
	}
}
void insert(int x)
{
	cnt ++; key[cnt] = x; wei[cnt] = rand1(), siz[cnt] = 1;
	bal t = split(root, x);
	root = merge(merge(t.a, cnt), t.b);
}
void erase(int x)
{
	bal wtz = split(root, x);
	bal gyx = split(wtz.b, x + 1);
	gyx.a = merge(son[gyx.a][0], son[gyx.a][1]);
	root = merge(wtz.a, merge(gyx.a, gyx.b));
}
int find1(int x)
{
	bal wtz = split(root, x);
	int res = siz[wtz.a] + 1;
	root = merge(wtz.a, wtz.b);
	return res;
}
int find2(int x)
{
	int pos = root;
	while (1)
	{
		if (siz[son[pos][0]] + 1 == x) return key[pos];
		if (siz[son[pos][0]] >= x) pos = son[pos][0];
		else x -= siz[son[pos][0]] + 1, pos = son[pos][1];
	}
}
int lst(int x) { return find2(find1(x) - 1); }
int nxt(int x) { return find2(find1(x + 1)); }
int main()
{
	cin >> n;
	int op, x;
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d %d", &op, &x);
		if (op == 1) insert(x);
		else if (op == 2) erase(x);
		else if (op == 3) printf("%d\n", find1(x));//val->rank
		else if (op == 4) printf("%d\n", find2(x));//rank->val
		else if (op == 5) printf("%d\n", lst(x));
		else if (op == 6) printf("%d\n", nxt(x));
	}
	return 0;
}

参考文献 https://www.luogu.com.cn/article/vj041eul