FHQ-Treap
概述
FHQ-Treap，又名无旋 Treap。
显然，FHQ-Treap 不使用旋转操作来维护平衡，他利用分裂和合并两个操作维护平衡。
定义结构体
放个代码
const int N = 1e5 + 10;
int tot, root;
struct FHQ_Treap {
int l, r, val, key, siz;
} tr[N];
#define lc tr[p].l
#define rc tr[p].r
void update(int p) { // 更新 p 的子树大小
tr[p].siz = tr[lc].siz + tr[rc].siz + 1;
}
void create(int &p, int x) { // 新建一棵只有一个节点的 Treap
p = ++tot;
tr[p].val = x;
tr[p].key = wdz();
tr[p].siz = 1;
}
分裂
分裂操作和两个参数有关，根节点 \(i\) 和关键值 \(key\)。
分裂操作分为按值分类和按排名分类两种，这里以按值分类为例。
分裂操作就是将一棵 Treap 按权值裁成小于等于 \(key\) 或者大于 \(key\) 的两棵 Treap。
放上代码：
void split(int p, int k, int &x, int &y) {
// 根节点，关键值，以及分裂后的两个节点
if (!p) {
x = y = 0;
return;
}
if (tr[p].val <= k) { // 权值小于等于 k
x = p; // 左子树全部属于第一个子树
split(rc, k, rc, y); // 分裂右子树
} else {
y = p;
split(lc, k, x, lc);
}
update(p);
}
合并
合并操作就是将两棵 Treap 合并成一棵 Treap。
由于此时两棵 Treap 中，一棵绝对严格小于另一棵。因此我们此时只需要维护堆的性质即可。
因此关键在于将谁作为谁的什么子树。
反复递归即可（和线段树合并的代码还是很像的）。
int merge(int x, int y) { // 返回合并后的树根
if (!x || !y) {
return x + y;
}
if (tr[x].key < tr[y].key) { // x 的优先级小于 y 的优先级
tr[x].r = merge(tr[x].r, y);
// 将子树 y 并入子树 x 的右子树
update(x);
return x;
} else {
tr[y].l = merge(x, tr[y].l);
update(y);
return y;
}
}
插入
假设要插入的数是 \(x\)，那么我们按照 \(x\) 讲 Treap 分裂成 \(a,b\) 两部分，将 \(x\) 与 \(a\) 合并，再与 \(b\) 合并即可。
split(root, k, x, y);
create(now, k);
root = merge(merge(x, now), y);
删除
我们考虑先将小于等于 \(x\) 的部分与大于 \(x\) 的部分分离。对于第一部分，我们再将小于 \(x\) 的部分和等于 \(x\) 的部分分离，最后中间删除等于 \(x\) 的部分即可。
split(root, k, x, tmp);
split(x, k - 1, x, y);
// 分离子树
y = merge(tr[y].l, tr[y].r);
// 合并 x 的子树，也就是去掉 x
root = merge(merge(x, y), tmp);
查询
查询就是查询排名为几的数。
int kth(int p, int k) { // 查询在 p 及其子树中排名为 k 的数
if (k == tr[lc].siz + 1) { // 为当前节点
return tr[p].val;
}
if (k <= tr[lc].siz) { // 在左子树中
return kth(lc, k);
} else { // 在右子树中
return kth(rc, k - tr[lc].siz - 1);
}
}
代码
// P3369【模板】普通平衡树
#include <bits/stdc++.h>
using namespace std;
mt19937 wdz(time(0));
const int N = 1e5 + 10;
int tot, root;
struct FHQ_Treap {
int l, r, val, key, siz;
} tr[N];
#define lc tr[p].l
#define rc tr[p].r
void update(int p) { // 更新 p 的子树大小
tr[p].siz = tr[lc].siz + tr[rc].siz + 1;
}
void create(int &p, int x) { // 新建一棵只有一个节点的 Treap
p = ++tot;
tr[p].val = x;
tr[p].key = wdz();
tr[p].siz = 1;
}
void split(int p, int k, int &x, int &y) {
// 根节点，关键值，以及分裂后的两个节点
if (!p) {
x = y = 0;
return;
}
if (tr[p].val <= k) { // 权值小于等于 k
x = p; // 左子树全部属于第一个子树
split(rc, k, rc, y); // 分裂右子树
} else {
y = p;
split(lc, k, x, lc);
}
update(p);
}
int merge(int x, int y) { // 返回合并后的树根
if (!x || !y) {
return x + y;
}
if (tr[x].key < tr[y].key) { // x 的优先级小于 y 的优先级
tr[x].r = merge(tr[x].r, y);
// 将子树 y 并入子树 x 的右子树
update(x);
return x;
} else {
tr[y].l = merge(x, tr[y].l);
update(y);
return y;
}
}
int kth(int p, int k) { // 查询在 p 及其子树中排名为 k 的数
if (k == tr[lc].siz + 1) { // 为当前节点
return tr[p].val;
}
if (k <= tr[lc].siz) { // 在左子树中
return kth(lc, k);
} else { // 在右子树中
return kth(rc, k - tr[lc].siz - 1);
}
}
int qq;
int now, tmp, x, y;
int main() {
scanf("%d", &qq);
while (qq--) {
int op, k;
scanf("%d%d", &op, &k);
if (op == 1) {
// 插入 k
split(root, k, x, y);
create(now, k);
root = merge(merge(x, now), y);
} else if (op == 2) {
// 删除 k
split(root, k, x, tmp);
split(x, k - 1, x, y);
// 分离子树
y = merge(tr[y].l, tr[y].r);
// 合并 x 的子树，也就是去掉 x
root = merge(merge(x, y), tmp);
} else if (op == 3) {
// 查询 k 数的排名
split(root, k - 1, x, y); // 分离子树
printf("%d\n", tr[x].siz + 1); // 节点数即为排名
root = merge(x, y);
} else if (op == 4) {
// 查询排名为 k 的数
printf("%d\n", kth(root, k));
} else if (op == 5) {
// 前驱
split(root, k - 1, x, y);
printf("%d\n", kth(x, tr[x].siz));
root = merge(x, y);
} else {
// 后继
split(root, k, x, y);
printf("%d\n", kth(y, 1));
root = merge(x, y);
}
}
return 0;
}