FHQ-Treap - 洛谷保存站

## FHQ-Treap

即**无旋转** Treap，代码长度短，好写好调，同时支持维护序列和可持久化。

首先在它是建立在 Treap 的基础上的，需要同时满足以下性质：

* 是二叉搜索树，是平衡树所有操作的基础。
  
* 是一个堆，这里堆的权值是一个一开始确定的随机权值 $rnd$，在后面的代码中是按大根堆的方式实现的。

由于权值是随机的，可以证明同时满足这两个性质的树的树高一定为 $O(\log n)$ 级别，保证了平衡树单次操作 $O(\log n)$ 的复杂度。

因此我们只需要实现一种可以快速维护这两个条件的数据结构，下面是 FHQ 的一些操作及实现解释。

### 分裂

我们需要分裂和合并来满足这两个性质。

首先是**分裂**，这里有两种写法，我写的是将一棵子树内 $val\le k$ 的点分裂出来成一颗新的树。（这里还有一种直接取中序前 $k$ 个的，原理类似。）

其实就是把按中序遍历的一段前缀取出来，需要使得可以发现此时分裂出来的树和原来的树均仍然满足限制。

```cpp
il void split(int x,tmp v,int &l,int &r){
    if(!x)return l=r=0,void();
    if(t[x].val<=v)l=x,split(t[x].rc,v,t[x].rc,r);
    else r=x,split(t[x].lc,v,l,t[x].lc);
    pushup(x);
}
```

这里的 $l,r$ 是分裂后的两个子树的根，注意 $l$ 是前 $v$ 个，顺序不能反了。

分的时候直接比较 $v$ 和当前的 $val_x$，小于等于就说明分界点一定在右边（左边的全部满足了），此时 $l$ 就确定下来为 $x$，然后递归进入右子树寻找。

把 $rc_x$ 传引用进去是因为如果直接切可能会碎成很多块，所以我们需要让碎开的部分也可以拼起来，就直接下面的块接在 $x$ 的右儿子上即可。

$v>val_x$ 同理。记得最后要 upd。

### 合并

合并的时候就需要考虑 $rnd$ 是堆的性质的影响了。

```cpp
il int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rnd>=t[y].rnd)return t[x].rc=merge(t[x].rc,y),pushup(x),x;
    else return t[y].lc=merge(x,t[y].lc),pushup(y),y;
}
```

这里的 $l,r$ 是合并的两个子树的编号，返回值代表合并后的根节点的编号。注意为了满足二叉搜索树，$l$ 中的 $val$ 是要小于 $r$ 的。

如果 $rnd_l\ge rnd_r$，说明 $l$ 要在 $r$ 的上面，首先返回的肯定是 $l$，$l$ 的左节点就是原来的左节点。

此时 $l$ 的右节点需要和 $r$ 进行合并操作，递归下去即可。

这两个操作的复杂度都是 $O(\log n)$ 的。

### 插入

为了实现方便，FHQ-Treap 中可以有多个不同的值，所以不需要判断是否出现过了。

可以考虑先分裂出 $\le v$ 和 $>v$ 的部分，此时 $v$ 就应该在两个中间，我们创建一个只有 $v$ 的子树，然后三个按顺序合并即可。

### 删除

首先还是把 $>v$ 的无关部分分出去。我们再把 $<v$ 的丢出去，此时剩下的这个全为 $v$ 的子树考虑直接删掉根节点，即将左右儿子 merge 起来。然后按顺序加回去即可。

### 查询值的排名

直接把 $<v$ 的分裂出去看大小即可，最后记得合并回来。

### 查询排名的值

FHQ-Treap 本身就是二叉搜索树，采用这个性质直接搜即可。

### 前驱后继

也可以偷懒。分出 $<v$ 的，此时这棵子树的最大值就是排名为 $siz_x$ 的，然后调用上面的查排名找到即可。

后继同理。

实现起来挺简单的，只写了 1.6k

正在渲染内容...