FHQ Treap
文章目录
FHQ yyds !
FHQ Treap
极为简洁,无需各种勾八左旋右旋
FHQ Treap 就像普通 Treap 一样,每个节点除了 val 以外还有个随机权值 rnd,val 符合 BST 的特征,rnd 符合堆的特征
我们把左旋右旋丢掉,通过两种操作 split 和 merge 大力维护平衡树
定义
为了方便阅读,先扔出定义代码
root 是全局根节点, num_node 是节点数量
int root, num_node;
struct Treap_Node
{
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define val(p) t[p].val
#define rnd(p) t[p].rnd
#define size(p) t[p].size
int ls, rs, rnd, val, size;
} t[N];
void update_size(int p) { size(p) = size(ls(p)) + size(rs(p)) + 1; }
split
大力拆拆拆
一般我们有两种方式拆分一棵树,按 val 或者 size 把一棵树 split 成两坨,一坨扔到左边,一坨扔到右边,左边那坨树的根节点为 x,右边那坨树的根节点为y
这里拿 按 val 拆分举例
p为我们当前访问的点,假如 p 的 val 小于等于 k,我们就把他扔进左树(小于等于val),然后进入 p 的右子树( BST 中 val 按中序递增),递归处理
反之同理
void split(int p, int k, int &x, int &y)
{
if (!p)
{
x = y = 0;
return;
}
if (val(p) <= k)
{
x = p;
split(rs(x), k, rs(x), y);
update_size(x);
}
else
{
y = p;
split(ls(y), k, x, ls(y));
update_size(y);
}
}
merge
大力 mer mer merge
注意要按照 rnd 合并,才能保证树的期望高度
我这份代码是将 rnd 按照小根堆的形式 merge 的
别忘了 x 是我们之前 split 出来的左边那坨小树的根节点,y则反之
如果 rnd(x) 小于 rnd(y) 那么我们这个小根堆 x 就在上面对吧,把 y 和 x 的右子树扔到一起,递归 merge
反之同理
int merge(int x, int y)
{
if (!x or !y)
return x | y;
if (rnd(x) < rnd(y))
{
rs(x) = merge(rs(x), y);
update_size(x);
return x;
}
else
{
ls(y) = merge(x, ls(y));
update_size(y);
return y;
}
}
插入一个值为 val 的节点
大力插插插
先 new_node 一个节点
然后我们大力 split 把树拆成 一坨比 val 小的 和 一坨比 val 大的
拆完了把这两棵树和我们刚刚新建的节点,总共三坨东西大力 merge
void new_node(int &k, int val)
{
val(++num_node) = val;
size(num_node) = 1;
rnd(num_node) = rand();
ls(num_node) = rs(num_node) = 0;
k = num_node;
}
void push(int &root, int val)
{
int x = 0, y = 0, z = 0;
split(root, val, x, y);
new_node(z, val);
root = merge(merge(x, z), y);
}
删除一个值为 val 的节点
大力删删删
和插入差不多
把树大力拆成 比 val 大的 和 比 val 小的
瞒着 val 偷偷 merge
void pop(int &root, int val)
{
int x = 0, y = 0, z = 0;
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(ls(y), rs(y));
root = merge(merge(x, y), z);
}
查询 val 的 rank
把小于 val 的节点大力 split 出来
看看 split 出来那坨东西的 size 大小就知道 rank 了
int query_rank_by_val(int &root, int val)
{
int x = 0, y = 0;
split(root, val - 1, x, y);
int rank = size(x) + 1;
root = merge(x, y);
return rank;
}
查询 rank 的 val
从根节点一路往下跑,康康什么时候当前节点的左子树的 size + 1 等于 rank 了,当前节点的 val 就是我们要找的,没跑到就递归下去跑
int query_val_by_rank(int p, int rank)
{
if (rank == size(ls(p)) + 1)
return val(p);
else if (rank <= size(ls(p)))
return query_val_by_rank(ls(p), rank);
else
return query_val_by_rank(rs(p), rank - size(ls(p)) - 1);
}
查前驱
大力查查 val 的 rank,再查查 rank - 1 的 val 就好啦
int query_prev(int &root, int val)
{
int x = 0, y = 0, k = 0, prev = 0;
split(root, val - 1, x, y);
if (!x)
return -INF;
k = size(x);
prev = query_val_by_rank(x, k);
root = merge(x, y);
return prev;
}
查后继
与前驱同理
int query_next(int &root, int val)
{
int x = 0, y = 0 , next = 0;
split(root, val, x, y);
if (!y)
return INF;
next = query_val_by_rank(y, 1);
root = merge(x, y);
return next;
}
平衡树模板题
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <stdlib.h>
const int N = 1e5 + 5;
const int INF = 2147483647;
int root, num_node;
struct Treap_Node
{
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define val(p) t[p].val
#define rnd(p) t[p].rnd
#define size(p) t[p].size
int ls, rs, rnd, val, size;
} t[N];
void update_size(int p) { size(p) = size(ls(p)) + size(rs(p)) + 1; }
void new_node(int &k, int val)
{
val(++num_node) = val;
size(num_node) = 1;
rnd(num_node) = rand();
ls(num_node) = rs(num_node) = 0;
k = num_node;
}
int merge(int x, int y)
{
if (!x or !y)
return x | y;
if (rnd(x) < rnd(y))
{
rs(x) = merge(rs(x), y);
update_size(x);
return x;
}
else
{
ls(y) = merge(x, ls(y));
update_size(y);
return y;
}
}
void split(int p, int k, int &x, int &y)
{
if (!p)
{
x = y = 0;
return;
}
if (val(p) <= k)
{
x = p;
split(rs(x), k, rs(x), y);
update_size(x);
}
else
{
y = p;
split(ls(y), k, x, ls(y));
update_size(y);
}
}
void pop(int &root, int val)
{
int x = 0, y = 0, z = 0;
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(ls(y), rs(y));
root = merge(merge(x, y), z);
}
void push(int &root, int val)
{
int x = 0, y = 0, z = 0;
split(root, val, x, y);
new_node(z, val);
root = merge(merge(x, z), y);
}
int query_val_by_rank(int p, int rank)
{
if (rank == size(ls(p)) + 1)
return val(p);
else if (rank <= size(ls(p)))
return query_val_by_rank(ls(p), rank);
else
return query_val_by_rank(rs(p), rank - size(ls(p)) - 1);
}
int query_rank_by_val(int &root, int val)
{
int x = 0, y = 0;
split(root, val - 1, x, y);
int rank = size(x) + 1;
root = merge(x, y);
return rank;
}
int query_prev(int &root, int val)
{
int x = 0, y = 0, k = 0, prev = 0;
split(root, val - 1, x, y);
if (!x)
return -INF;
k = size(x);
prev = query_val_by_rank(x, k);
root = merge(x, y);
return prev;
}
int query_next(int &root, int val)
{
int x = 0, y = 0 , next = 0;
split(root, val, x, y);
if (!y)
return INF;
next = query_val_by_rank(y, 1);
root = merge(x, y);
return next;
}
int read()
{
int x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int main()
{
int n = read();
while (n--)
{
int opt = read(), x = read();
switch (opt)
{
case 1:
push(root, x);
break;
case 2:
pop(root, x);
break;
case 3:
printf("%d\n", query_rank_by_val(root, x));
break;
case 4:
printf("%d\n", query_val_by_rank(root, x));
break;
case 5:
printf("%d\n", query_prev(root, x));
break;
case 6:
printf("%d\n", query_next(root, x));
break;
}
}
return 0;
}