浅谈 FHQ Treap
目录简单介绍
FHQ Treap,以下简写为 \(fhq\)，是一种treap(树堆)的变体，功能比treap强大。
\(fhq\) 不需要通过一般平衡树的左右旋转来保持平衡，而是通过分裂 \(split\)和合并 \(merge\) 来实现操作。
优点是比较好理解、代码短、上手快、可持久化
主要是不用像 \(splay\) 一样旋来旋去。
Treap比较好玩的一点是，它整体是拥有二叉搜索树的性质，但是它的每一个节点都会有一个附加权值，它的附加权值是符合堆的性质。
这样我们可以明显看出，这棵树的形态(平衡与否)是由这个附加权值决定的。
那我们该如何取这个权值呢？随机！！
是的，我们每次都随机一个权值作为它的附加权值，那么它就大概是平衡的。
只需要两个基础操作，就可以达到splay的所有功能
前置操作
结构
对于每个树上节点开一个结构体，维护左儿子、右儿子、两个权值、还有子树中的节点个数。
然后给定一个树上的权值 \(v\) ，新建节点，还有更新子树大小 \(update\)。
struct fhq {
int l , r , v , t , sz;
} tr[N];
void update (int x) { tr[x].sz = 1 + tr[tr[x].l].sz + tr[tr[x].r].sz; }
int new_pos (int v) {
tr[++pos].sz = 1;
tr[pos].v = v;
tr[pos].t = rnd ();
return pos;
}
\(rnd()\) 是随机数生成函数，需要搞一个预处理
std::mt19937 rnd(233);
分裂 split
这个的主要思想就是把一个 \(treap\) 按照一个权值 \(v\) 分成两个。
把所有小于等于 \(v\) 的分到一棵树中，把所有大于 \(v\) 的分到另一棵树中，如下图。
可以对照代码感性理解一下
void split (int now , int k , int &x , int &y) {
if (now == 0) x = y = 0;
else {
if (tr[now].v <= k)
x = now , split (tr[now].r , k , tr[now].r , y);
else
y = now , split (tr[now].l , k , x , tr[now].l);
update (now);
}
}
合并 merge
\(merge\) 操作按照堆权合并x,y两颗子树,合并前要保证x子树中的权值<y子树中的权值，如下图。
图中黄字为堆权
int merge (int x , int y) {
if (x == 0 || y == 0) return x + y;
if (tr[x].t < tr[y].t) {
tr[x].r = merge (tr[x].r , y);
update (x);
return x;
}
else {
tr[y].l = merge (x , tr[y].l);
update (y);
return y;
}
}
一般操作
Insert
插入一个权值为 \(v\) 的点，把树按照 \(v\) \(split\) 成两个，再按照顺序合并。
split (rt , a , x , y);
rt = merge (merge (x , new_pos (a)) , y);
delete
删除权值为 \(v\) 的点，需要 \(split\) 两次。一次按照 \(v\) 分成 \(x , z\) ，一次把 \(x\) 按照 \(v - 1\) 分成 \(x , y\) ，那么 \(y\) 的中间点就是 \(v\) ，把 \(y\) 的两个儿子直接合并也就相当于删除了 \(v\) ，然后再按照顺序把其他节点合并就好了。
split (rt , a , x , z);
split (x , a - 1 , x , y);
y = merge (tr[y].l , tr[y].r);
rt = merge (merge (x , y) , z);
查询排名为 \(x\) 的数
就是普通的查询，每次把 \(x\) 和当前节点的左子树大小比较即可。
int kth (int now , int k) {
while (1) {
if (k <= tr[tr[now].l].sz)
now = tr[now].l;
else if (k == tr[tr[now].l].sz + 1)
return now;
else
k -= tr[tr[now].l].sz + 1 , now = tr[now].r;
}
}
查询 \(v\) 的排名 rank
把原树 \(split\) 按照 \(v - 1\) 成 \(x , y\) ，\(x\) 的大小 \(+1\) 即为 \(x\) 的排名。
split (rt , a - 1 , x , y);
printf ("%d\n" , tr[x].sz + 1);
rt = merge (x , y);
查询 \(x\) 的前驱 precursor
找前驱的话把原树按 \(v-1\) \(split\)成 \(x,y\)，在 \(x\) 里面找最大值。
split (rt , a - 1 , x , y);
printf ("%d\n" , tr[kth (x , tr[x].sz)].v);
rt = merge (x , y);
查询 \(x\) 的后继 successor
跟前驱类似。把原树按 \(v\) \(split\) 成 \(x,y\)，在 \(y\) 里找最小值。
split (rt , a , x , y);
printf ("%d\n" , tr[kth (y , 1)].v);
rt = merge (x , y);
版题
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 5e5 + 5;
std::mt19937 rnd(233);
int pos , rt;
struct fhq {
int l , r , v , t , sz;
} tr[N];
void update (int x) { tr[x].sz = 1 + tr[tr[x].l].sz + tr[tr[x].r].sz; }
int new_pos (int v) {
tr[++pos].sz = 1;
tr[pos].v = v;
tr[pos].t = rnd ();
return pos;
}
void split (int now , int k , int &x , int &y) {
if (now == 0) x = y = 0;
else {
if (tr[now].v <= k)
x = now , split (tr[now].r , k , tr[now].r , y);
else
y = now , split (tr[now].l , k , x , tr[now].l);
update (now);
}
}
int merge (int x , int y) {
if (x == 0 || y == 0) return x + y;
if (tr[x].t < tr[y].t) {
tr[x].r = merge (tr[x].r , y);
update (x);
return x;
}
else {
tr[y].l = merge (x , tr[y].l);
update (y);
return y;
}
}
int kth (int now , int k) {
while (1) {
if (k <= tr[tr[now].l].sz)
now = tr[now].l;
else if (k == tr[tr[now].l].sz + 1)
return now;
else
k -= tr[tr[now].l].sz + 1 , now = tr[now].r;
}
}
int main () {
int T , op , a , x , y , z;
scanf ("%d" , &T);
while (T --) {
scanf ("%d%d" , &op , &a);
if (op == 1) {
split (rt , a , x , y);
rt = merge (merge (x , new_pos (a)) , y);
}
else if (op == 2) {
split (rt , a , x , z);
split (x , a - 1 , x , y);
y = merge (tr[y].l , tr[y].r);
rt = merge (merge (x , y) , z);
}
else if (op == 3) {
split (rt , a - 1 , x , y);
printf ("%d\n" , tr[x].sz + 1);
rt = merge (x , y);
}
else if (op == 4)
printf ("%d\n" , tr[kth (rt , a)].v);
else if (op == 5) {
split (rt , a - 1 , x , y);
printf ("%d\n" , tr[kth (x , tr[x].sz)].v);
rt = merge (x , y);
}
else {
split (rt , a , x , y);
printf ("%d\n" , tr[kth (y , 1)].v);
rt = merge (x , y);
}
}
return 0;
}