FHQ treap
参考: 链接
Treap:
优点: 码量小 好写 核心代码是复读机
好理解 支持操作多
缺点: 常数大了点
维护平衡的奇怪操作:
Treap: 旋转
FHQ Treap: 分裂 合并
节点信息
- 左右子树编号
- 值
- 索引
- 子树大小
struct node
{
int l, r;
int val, key;
int size;
}fhq[N];
int cnt, root;
//建立新节点
inline int New(int val)
{
fhq[++ cnt].val = val;
fhq[cnt].key = rand();
fhq[cnt].size = 1;
return cnt;
}
分裂(split)
有2种：按值分裂，按大小分裂
按值分裂
把树拆成两棵树，拆出来的一棵树的值全部小于等于给定的值，另外一部分的值全部大于给定的值
按大小分裂
把树拆成两棵树，拆出来的一棵树的大小等于给定的大小，另外一部分在另一颗树里
(一般当平衡树时用按值分裂)
(维护区间信息的时候按大小分裂, 最经典的就是文艺平衡树)
分裂->
inline void update(int now)
{
fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
}
void split(int now, int val, int &x, int &y)
{
if(!now) x = y = 0;
else
{
if(fhq[now].val <= val)
{
x = now;
split(fhq[now].r, val, fhq[now].r, y);
}
else
{
y = now;
split(fhq[now].l, val, x, fhq[now].l);
}
update(now);
}
}
合并
把两棵树x, y合并成一棵树(x树上的所有值都小于等于y树上的所有值, 并且新合并出来的树满足treap的性质)
合并->
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(fhq[x].key > fhq[y].key) // < > <= >=都可以
{
fhq[x].r = merge(fhq[x].r, y);
update(x);
return x;
}
else
{
fhq[y].l = merge(x, fhq[y].l);
update(y);
return y;
}
}
插入
设插入的值为val
- 按值val把树分裂成x, y
- 合并x, 新节点, y
int x, y, z;
inline void insert(int val)
{
split(root, val, x, y);
root = merge(merge(x, New(val)), y);
}
删除
- 按照值val把树分为x, z
- 再按值val-1把x分为x和y
- y树上值全部等于val, 去掉它的根节点:让y等于合并y的左子树和右子树
- 合并x, y, z
inline void del(int val)
{
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(fhq[y].l, fhq[y].r);
root = merge(merge(x, y), z);
}
查询排名
- 按值val-1分裂成x, y
- x的大小+1就是val的排名
- 把x, y合并
inline int getrank(int val)
{
split(root, val - 1, x, y);
int rank = fhq[x].size;
root = merge(x, y);
return rank + 1;
}
查询排名的值
inline int getsum(int rank)
{
int now = root;
while(now)
{
if(fhq[fhq.l].size + 1 == rank)
break;
else if(fhq[fhq[now].l].size >= rank)
now = fhq[now].l;
else
{
rank -= fhq[fhq[now].l].size + 1;
now = fhq[now].r;
}
}
return fhq[now].val;
}
前驱/后继
前驱: 按值val-1分裂成x, y, x里面最右的数就是val的前驱
后继: 按值val分裂成x, y, 则y里面最左的数就是val的后继
inline int pre(int val)
{
split(root, val - 1, x, y);
int now = x;
while(fhq[now].r)
now = fhq[now].r;
int res = fhq[now].val;
root = merge(x, y);
return res;
}
inline int nxt(int val)
{
split(root, val, x, y);
while(fhq[now].l)
now = fhq[now].l;
int res = fhq[now].val;
root = merge(x, y);
return res;
}
不储存索引的fhq treap
只有在merge函数才有维护随机的操作
把merge操作里面改为随机的数据也可以
fhq treap的区间操作
P3391 文艺平衡树
链表\(O(n^2)\)
Splay或fhq treap\(O(nlogn)\)
实现区间操作:
设要操作的区间为[l, r], 我们就把这一段split出来操作然后合并回去
具体步骤:
- 把fhq treap按大小l-1拆分成x, y
- 把y按大小r-l+1拆分成y和z
- y树就是要操作的区间的平衡树
- 合并回去xyz
解决文艺平衡树
懒标记: 当我们想对一个区间进行翻转, 就对这个区间维护懒标记: 如果原来没有, 就加上; 如果原来有, 那就去掉
别忘了写懒标记pushdown操作, 如果当前节点左右子树有被更改的风险那就下传
struct node
{
int l, r;
int val, key;
int size;
bool reverse;
}fhq[N];
int cnt, root;
inline int New(int val)
{
fhq[++ cnt].val = val;
fhq[cnt].key = rand();
fhq[cnt].size = 1;
return cnt;
}
inline void update(int now)
{
fhq[now].size = fhq[fhq[l]].size + fhq[fhq[now].r].size + 1;
}
inline void pushdown(int now)
{
swap(fhq[now].l, fhq[now].r);
fhq[fhq[now].l].reverse ^= 1;
fhq[fhq[now].r].reverse ^= 1;
fhq[now].reverse = false;
}
void split(int now, int siz, int &x, int &y)
{
if(!now) x = y = 0;
else
{
if(fhq[now].reverse) pushdown(now);
if(fhq[fhq[now].l].size < siz)
{
x = now;
split(fhq[now].r, siz - fhq[fhq[now].l].size - 1, fhq[now].r, y);
}
else
{
y = now;
split(fhq[now].r, siz, x, fhq[now].l)
}
update(now);
}
}
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(fhq[x].key < fhq[y].key)
{
if(fhq[x].reverse) pushdown(x);
fhq[x].r = merge(fhq[x].r, y);
update(x);
return x;
}
else
{
if(fhq[y].reverse) pushdown(y);
fhq[y].l = merge(x, fhq[y].l);
update(y);
return y;
}
}
void reverse(int l, int r)
{
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);
fhq[y].reverse ^= 1;
root = merge(merge(x, y), z);
}
void ldr(int now)
{
if(!now) return;
if(fhq[now].reverse) pushdown(now);
ldr(fhq[now].l);
printf("%d ", fhq[now].val);
ldr(fhq[now].r);
}