【学习笔记】fhq Treap
NCC79601
2019-10-20 16:03:28
fhq Treap 是一种极其简易好写的平衡树，其本质上是一个可并堆 + BST。所以可以先复习一下 [左偏树](https://ncc79601.blog.luogu.org/leftist-tree) 的相关写法，再来复习 fhq Treap。
# 拼树与拆树
普通的 Treap 中，需要通过 Zig / Zag 操作来完成对堆性质的维护。但在 fhq Treap 当中，我们可以直接把树拆掉，然后按堆的性质拼在一起即可。
## 合并
按照小根堆的性质合并即可。
```cpp
inline int merge(int x, int y) {
if (!x || !y)
return x + y;
if (p(x) < p(y)) {
r(x) = merge(r(x), y);
update(x);
return x;
// 这一段比较绕
} else {
l(y) = merge(x, l(y));
update(y);
return y;
}
}
```
## 拆分
split() 操作又分 **按值分离** 和 **按大小分离** 两种；其中按大小分离用于区间翻转，此处需要按值分离。
split(now, k, &x, &y) 函数的意思即把以$now$为根的子树的所有节点，小于等于$k$的分到$x$中，大于$k$的分到$y$中。结合代码理解。
```cpp
inline void split(int now, int k, int &x, int &y) {
if (!now) {
x = y = 0;
return ;
}
if (v(now) <= k) {
// now 在 x 当中
x = now;
split(r(now), k, r(now), y);
} else {
// now 在 y 当中
y = now;
split(l(now), k, x, l(now));
}
update(now);
return ;
}
```
# 插入
插入一个值为$c$的点，就直接把整棵树拆成两半，把$c$接进来，然后再合并即可。**足够暴力**。
```cpp
inline void insert(int c) {
int x, y;
split(root, c, x, y);
root = merge(merge(x, new_node(c)), y);
return ;
}
```
# 删除
直接把树拆到$c$为某个子树的根，然后把$c$的左右儿子合并起来，就把$c$删掉了。
```cpp
inline void erase(int c) {
int x, y, z;
split(root, c, x, z);
split(x, c - 1, x, y);
// 这里也比较绞
y = merge(l(y), r(y));
root = merge(merge(x, y), z);
return ;
}
```
# 第$k$大数
此处与普通 Treap 并无大异。
```cpp
inline int kth(int now, int k) {
while (now) {
if (k == s(l(now)) + 1)
return v(now);
if (k <= s(l(now)))
now = l(now);
else {
k -= s(l(now)) + 1;
now = r(now);
}
}
return 0;
}
```
# 排名
把树按照$c$为关键字拆了，然后查树的大小即可。简单粗暴。
```cpp
inline int rank(int c) {
int x, y;
split(root, c - 1, x, y);
int res = s(x) + 1;
// 注意这里的严格性
root = merge(x, y);
return res;
}
```
# 前驱后继
把树按照$c-1$或者$c$为关键字拆掉，然后对于拆出来的某棵树查询树中最大 / 最小值即可。
```cpp
inline int prefix(int c) {
int x, y;
split(root, c - 1, x, y);
// 这里是 c - 1
int res = kth(x, s(x));
root = merge(x, y);
return res;
}
inline int suffix(int c) {
int x, y;
split(root, c, x, y);
// 这里是 c
int res = kth(y, 1);
root = merge(x, y);
return res;
}
```
# 总结
fhq Treap 不仅支持**所有平衡树的操作**（包括区间翻转等 Splay 特性；仅在 LCT 中比 Splay 多了个$logn$，然而那和我有什么关系呢），而且常数与 Splay 接近，更重要的是简单好写、代码量少。所以还写个毛线的替罪羊树，直接 split() 然后 merge() 解决一切问题。
---
下面记录一个 class 封装好的 fhq Treap，考场上当然是不用封装，直接写全局函数即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
template <typename T> class fhq_treap {
private:
int root, tot;
struct BinarySearchTree {
T val;
int pri, size, lson, rson;
#define v(x) tree[x].val
#define p(x) tree[x].pri
#define s(x) tree[x].size
#define l(x) tree[x].lson
#define r(x) tree[x].rson
} tree[MAXN];
inline void update(int now) {
s(now) = s(l(now)) + s(r(now)) + 1;
return ;
}
inline int new_node(T c) {
v(++tot) = c;
p(tot) = rand();
s(tot) = 1;
return tot;
}
inline int merge(int x, int y) {
if (!x || !y)
return x + y;
if (p(x) < p(y)) {
r(x) = merge(r(x), y);
update(x);
return x;
} else {
l(y) = merge(x, l(y));
update(y);
return y;
}
}
inline void split(int now, T k, int &x, int &y) {
if (!now) {
x = y = 0;
return ;
}
if (v(now) <= k) {
x = now;
split(r(now), k, r(now), y);
} else {
y = now;
split(l(now), k, x, l(now));
}
update(now);
return ;
}
public:
fhq_treap() {
root = 0;
tot = 0;
}
inline int _root() {
return root;
}
inline void insert(T c) {
int x, y;
split(root, c, x, y);
root = merge(merge(x, new_node(c)), y);
return ;
}
inline void erase(T c) {
int x, y, z;
split(root, c, x, z);
split(x, c - 1, x, y);
y = merge(l(y), r(y));
root = merge(merge(x, y), z);
return ;
}
inline T kth(int now, int k) {
while (now) {
if (k == s(l(now)) + 1)
return v(now);
if (k <= s(l(now)))
now = l(now);
else {
k -= s(l(now)) + 1;
now = r(now);
}
}
return 0;
}
inline int rank(T c) {
int x, y;
split(root, c - 1, x, y);
int res = s(x) + 1;
root = merge(x, y);
return res;
}
inline T prefix(T c) {
int x, y;
split(root, c - 1, x, y);
T res = kth(x, s(x));
root = merge(x, y);
return res;
}
inline T suffix(T c) {
int x, y;
split(root, c, x, y);
T res = kth(y, 1);
root = merge(x, y);
return res;
}
};
fhq_treap<int> bst;
int n;
int res, uz;
char ch;
inline int read() {
res = 0, uz = 1;
ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
uz = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
return res * uz;
}
int main() {
srand(time(0));
n = read();
for ( ; n; n--) {
switch (read()) {
case 1: {
bst.insert(read());
break;
}
case 2: {
bst.erase(read());
break;
}
case 3: {
printf("%d\n", bst.rank(read()));
break;
}
case 4: {
printf("%d\n", bst.kth(bst._root(), read()));
break;
}
case 5: {
printf("%d\n", bst.prefix(read()));
break;
}
default: {
printf("%d\n", bst.suffix(read()));
break;
}
}
}
return 0;
}
```
---
# 区间翻转
**惰性翻转**，然后在输出时 pushdown() 即可。结合代码感性理解。
（当然，可以认为线段树是这种方式的推广）
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
template <typename T> class fhq_treap {
private:
struct tree {
T v;
int p, s;
bool f;
tree *l, *r;
};
tree *root, *nul;
void update(tree *now) {
if (now == nul)
return ;
now->s = now->l->s + now->r->s + 1;
return ;
}
tree *new_node(T c) {
tree *_p;
_p = (tree *) malloc(sizeof(tree));
_p->l = _p->r = nul;
_p->v = c;
_p->p = rand();
_p->s = 1;
_p->f = false;
return _p;
}
void pushdown(tree *now) {
swap(now->l, now->r);
if (now->l != nul)
now->l->f ^= 1;
if (now->r != nul)
now->r->f ^= 1;
now->f = 0;
return ;
}
tree *merge(tree *x, tree *y) {
if (x == nul)
return y;
if (y == nul)
return x;
if (x->p < y->p) {
if (x->f)
pushdown(x);
x->r = merge(x->r, y);
update(x);
return x;
} else {
if (y->f)
pushdown(y);
y->l = merge(x, y->l);
update(y);
return y;
}
}
void split(tree *now, int k, tree *&x, tree *&y) {
if (now == nul) {
x = y = nul;
return ;
}
if (now->f)
pushdown(now);
if (now->l->s < k) {
x = now;
split(now->r, k - now->l->s - 1, now->r, y);
} else {
y = now;
split(now->l, k, x, now->l);
}
update(now);
return ;
}
public:
fhq_treap() {
nul = (tree *) malloc(sizeof(tree));
nul->s = 0;
root = nul;
}
tree *_root() {
return root;
}
void insert(T c) {
tree *x, *y;
split(root, c, x, y);
root = merge(merge(x, new_node(c)), y);
return ;
}
void reverse(tree *now, int l, int r) {
tree *x, *y, *z;
split(now, l - 1, x, y);
split(y, r - l + 1, y, z);
y->f ^= 1;
now = merge(merge(x, y), z);
return ;
}
void print(tree *now) {
if (now == nul)
return ;
if (now->f)
pushdown(now);
print(now->l);
printf("%d ", now->v);
print(now->r);
return ;
}
};
fhq_treap<int> bst;
int n, m;
int res, uz;
char ch;
inline int read() {
res = 0, uz = 1;
ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
uz = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + ch - 48;
ch = getchar();
}
return res * uz;
}
int main() {
srand(time(0));
n = read(), m = read();
for (int i = 1; i <= n; i++)
bst.insert(i);
for (int l, r; m; m--) {
l = read(), r = read();
bst.reverse(bst._root(), l, r);
}
bst.print(bst._root());
return 0;
}
```