速学 FHQ treap

_Cheems · 2023-11-07 20:21:29 · 个人记录

简介

听说是平衡树的扛把子，好写好调好理解，扩展性强、功能多，常数也不大。

基本

用结构体存点，以分裂、合并为基本操作，不需旋转即可维护 treap 性质。

• 分裂 split

先介绍以值划分：考虑以 val 为划分值，将 u 子树分为 \le val 和 > val 的两部分。

用引用实现，那么有如下定义：

void split(u, &x, &y, val)

关于 &x,&y，可以理解为两棵子树分别需要填的位置。

为何这样写？暴力是 O(n) 的，由于分裂过程中不会过多改变树的形态，所以只需调整每个节点的左、右儿子变量即可。引用可以胜任此任务。

给出代码：

inline void split(int u, int &x, int &y, int val){
    if(!u) {x = y = 0; return ;}
    if(t[u].s <= val) x = u, split(rt, rt, y, val);
    else y = u, split(lt, x, lt, val);
    psup(u);
}

理解：当前值不大于 val 时，先直接把 u 子树放在 x 位置上，然后调整 u 的右子树，同时更改 u 的右儿子指针。另一种情况同理。

• 合并 merge

类似线段树合并，用两个指针遍历两棵树：

int merge(x, y)

不需引用，函数返回为合并后的顶点，主要是为了后面操作方便。

还有一点：由于分裂和合并操作总是成对出现，所以默认 x 子树所有元素永远不大于 y 子树所有元素。接下来只需比较优先级即可。

inline int merge(int x, int y){
    if(!x || !y) return x + y; 
    if(t[x].rnd <= t[y].rnd) {t[x].rs = merge(t[x].rs, y), psup(x); return x;}
    else {t[y].ls = merge(x, t[y].ls), psup(y); return y;}
}

理解：开头是个小技巧，意思是返回两者中非零的那个；当 x 优先级不大于 y 优先级时，显然需将 y 放到 x 左下角。另一种情况差不多。

（此处维护小根堆）

常见操作

有了 split 和 merge 后便能完成大量操作。

• 插入 x：原树分裂为两部分，将 \le x 部分与 x 合并，再把它们与 >x 部分合并即可。

• 删除 x：分裂为 \le x 和 >x，\le x 再分为 \le x-1 和 =x。剔除 =x 部分的根合并其左右儿子，将它回溯地合并为原树即可。

• 求 x 排名：即为 <x 的数量 +1。分裂出来然后 siz+1。

• 求排名为 x：利用平衡树性质二分求解即可，和是什么平衡树没啥关系。

• 求 x 前驱 / 后继：<x 部分中排名最大的 / >x 部分中排名最小的。

进阶

我不到啊。