fhq-treap 是一种好写、复杂度低，且功能的优秀数据结构，涵盖了 treap 几乎所有的功能，其巧妙之处，就在于运用分离和合并两种操作代替了旋转操作。
1. BST 的定义
（摘自 OI Wiki）二叉搜索树（BST）是一种二叉树的树形数据结构，其定义如下：
- 空树是 BST
- 若 BST 左子树不为空，则其左子树上所有点的附加权值均小于根节点。
- 若 BST 右子树不为空，则其右子树上所有点的附加权值均大于根节点。
- BST 的左右子树均为 BST。
2. fhq-treap
2.1 需要存储的信息
左儿子 ls，右儿子 rs，子树大小 sz，权值 val 维护 tree 的性质，及随机优先级 key 维护 heap 的性质。
大体同 treap 相同，但 fhq-treap 不需要记录 val 重复次数 cnt，因为一般情况下，它不将权值相同节点视作一个节点。
2.2 更新答案 sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
2.3 基础操作：分裂、合并与新建节点
2.3.1 分裂 split
- 按照权值大小分裂
将原树 \(T\) 分成左右两个子树 \(T_l\), \(T_r\)。设当前节点为 \(p\):
\[1':\ val_p\leq v, p\in T_l,\ split\ rs_p\\
2':\ val_p> v, p\in T_r,\ split\ ls_p
\]
当 \(p=0\) 时停止 split。
void split(int p, int v, int &x, int &y) {
if (!p) {x = y = 0; return ;}
if (val[p] <= v) x = p, split(rs[p], v, rs[x], y);
else y = p, split(ls[p], v, x, ls[y]);
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
}
- 按照子树大小分裂
同理。
void split(int p, int v, int &x, int &y) {
if (!p) {x = y = 0; return ;}
if (v <= sz[ls[p]]) x = p, split(rs[p], v, rs[x], y);
else y = p, split(ls[p], v, x, ls[y]);
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
}
2.3.2 合并 merge
条件：合并的两棵树 \(T_x\) 和 \(T_y\) 必须满足一棵严格小于另一棵，此处设 \(T_x<T_y\)。
\[1': key_x>key_y, fa_y=x, rs_x\leftarrow merge(rs_x,y)
2': key_x\leq key_y, fa_x=y, ls_y\leftarrow merge(x,ls_y)
\]
当 \(x,y\) 不全非空停止 merge，使用类似线段树合并 trick，返回 \(x \or y\)
int merge(int x, int y) {
if (!x || !y) return x | y;
if (key[x] < key[y]) {
ls[y] = merge(x, ls[y]), sz[y] = sz[ls[y]] + sz[rs[y]] + 1;
return y;
} else {
rs[x] = merge(rs[x], y), sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
reutrn x;
}
}
2.3.1 新建节点
int nd(int v) {
int x = node++;
val[x] = v, rd[x] = rand(), sz[x] = 1;
return x;
}
2.4 更多基础功能
见普通平衡树模板题 P3369 【模板】普通平衡树
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 7;
int n, m, rt, node, ls[N], rs[N], val[N], rd[N], sz[N];
void push(int x) {sz[x] = sz[ls[x]] + sz[rs[x]] + 1;}
void spl(int p, int v, int &x, int &y) {
if (!p) {x = y = 0; return ;}
if (val[p] <= v) x = p, spl(rs[p], v, rs[x], y);
else y = p, spl(ls[p], v, x, ls[y]);
push(p);
}
int mer(int x, int y) {
if (!x || !y) return x | y;
if (rd[x] < rd[y]) {
ls[y] = mer(x, ls[y]), push(y);
return y;
} else {
rs[x] = mer(rs[x], y), push(x);
return x;
}
}
int nd(int v) {
int x = ++node;
val[x] = v, rd[x] = rand(), sz[x] = 1;
return x;
}
void ins(int v) {
int x = 0, y = 0;
spl(rt, v - 1, x, y), rt = mer(mer(x, nd(v)), y);
}
void del(int v) {
int x = 0, y = 0, z = 0;
spl(rt, v, x, z), spl(x, v - 1, x, y);
y = mer(ls[y], rs[y]), rt = mer(mer(x, y), z);
}
int kth(int k) {
int p = rt;
while (1) {
if (k <= sz[ls[p]]) p = ls[p];
else if (k == sz[ls[p]] + 1) return val[p];
else k -= sz[ls[p]] + 1, p = rs[p];
}
}
int pre(int v){
int p = rt, ans = 0;
while (1) {
if (!p) return ans;
else if (v <= val[p]) p = ls[p];
else ans = val[p], p = rs[p];
}
}
int suc(int v) {
int p = rt, ans = 0;
while (1) {
if (!p) return ans;
else if (v >= val[p]) p = rs[p];
else ans = val[p], p = ls[p];
}
}
int rnk(int v) {
int x = 0, y = 0, ans = 0;
spl(rt, v - 1, x, y), ans = sz[x] + 1;
return rt = mer(x,y), ans;
}
int main(){
cin >> n;
while (n--) {
int op, x;
cin >> op >> x;
if (op == 1) ins(x);
else if (op == 2) del(x);
else if (op == 3) cout << rnk(x) << endl;
else if (op == 4) cout << kth(x) << endl;
else if (op == 5) cout << pre(x) << endl;
else cout << suc(x) << endl;
}
return 0;
}