概述

FHQ Treap 基于 Treap 发明的“无旋 Treap”，代码短，易理解且速度快（在 OI 算是很优秀的算法了）。

FHQ Treap 核心函数只有两个，分别是分裂和合并。字面意思，就是将某一棵二叉查找树按某种要求分裂成两个或将两个合并成一个。

实现

变量维护

变量名	功能
root	记录所维护平衡树的根节点编号
cnt	节点总数
lson[i]	编号为 i 的节点的左儿子的编号
rson[i]	编号为 i 的节点的右儿子的编号
val[i]	编号为 i 的节点的值
siz[i]	编号为 i 的节点的子树的大小
cmp[i]	下文介绍

函数

分裂

通常分为按 v 合并或按 siz 合并。按 v 合并时，将小于等于 v 的和大于 v 分裂成两棵树。按 siz 分裂即将从小到大排前 siz 的和 siz 之后的分裂成两棵树。

以按 v 分裂的为例（另一类同理）。函数的参数有四个，分别为 u、v、x、y，分别代表当前节点，v（具体含义见上），以及分裂成的两个树的待接入的位置的地址。

若当前节点为 u ，则分为两种情况：

若 \(val[u] \leq v\)，则将 u 接到树 x 下面，继续分裂 rson[u]。
若 \(val[u] > v\)，则将 u 接到树 y 下面，继续分烈 lson[u]。

代码片段：

void Split(int u, int v, int &x, int &y) {
	if(!u) {x = y = 0; return;}
	if(val[u] <= v) x = u, Split(rson[u], v, rson[u], y);
	else y = u, Split(lson[u], v, x, lson[u]);
	PushUp(u);
}

合并

将两个子树合并成一棵树并返回根节点编号。为了防止极端情况两棵树合并后变成一条链（反正就是防止深度很大导致退化），类似 Treap 中的操作，我们给每个节点随机分配一个值 cmp，用来优化。

代码片段：

int Merge(int x, int y) {
	if(!x || !y) return x + y;
	if(cmp[x] < cmp[y]) {
		rson[x] = Merge(rson[x], y);
		PushUp(x);
		return x;
	}
	else {
		lson[y] = Merge(x, lson[y]);
		PushUp(y);
		return y;
	}
}

查询第 K 大

很好想，跟值域线段树查询第 K 大差不多。

代码片段：

int Get_Kth(int u, int k) {
	if(k <= siz[lson[u]]) return Get_Kth(lson[u], k);
	if(k == siz[lson[u]] + 1) return u;
	if(k >= siz[lson[u]] + 2) return Get_Kth(rson[u], k - siz[lson[u]] - 1);
	return 0;
}