FHQ-Treap学习笔记
wgyhm
·
·
个人记录
FHQ-Treap学习笔记
0 、引（che）言 (dan)
树 ( \mathtt{Tree} ) 堆 ( \mathtt{Heap} )，在数据结构中也称 \mathtt{Treap}，\mathtt{Treap} 就是这俩英文名的合成。是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。相对于其他的平衡二叉搜索树，\mathtt{Treap} 的特点是实现简单，且能基本实现随机平衡的结构。
每个结点除保存一个值两个子节点外，还保存一个随机权；不过不保存父结点，这就是 \mathtt{Treap} 码量小的原因。和其他平衡树一样，\mathtt{Treap} 的中序遍历值单调不减；而根据堆的性质，每个结点的权^{[1]}小于两个子结点的权。
* 那 $\mathtt{FHQ-Treap}$ 呢
$\mathtt{Treap}$ 分为有旋和无旋两种，而无旋 $\mathtt{Treap}$ 是由范浩强发明的，所以又叫 $\mathtt{FHQ-Treap}$。范浩强NB！
本文~~重点~~全部介绍 $\mathtt{FHQ-Treap}$。
当然文艺平衡树，以及其拓展我之后有时间就更。
## 1 、权值平衡树
### 基本信息
在一个节点中，我们要记录5个信息：
```
struct yyy{
int val;//当前节点的值
int rnd;//当前节点的权
int ls,rs;//当前节点的左儿子和右儿子
int size;//当前节点的子树大小
}
```
### 基本操作
$\mathtt{FHQ-Treap}$ 的核心操作有分裂和合并两个。
#### 分裂 ( $split$ )
~~因为只有分裂才能合并，所以我们先讲分裂~~。
分裂操作就是将一棵平衡树，分裂成两个平衡树。其中左边的一棵平衡树的所有节点的值小于 $x$，右边一棵平衡树的所有节点的值大于等于 $x$。
```cpp
struct FHQ_Treap{
zyq split(int k,int x){//zyq结构体中存贮的是两棵返回的平衡树的根节点值。
}
}
```
举个例子，$x=4:
当然因为我懒不想画所以我就用别人的图了
感谢 @zhy123456 的图片。
为了方便讲述，我们约定最后的两个平衡树，小于 x 的叫做 a 子树，大于等于 x 的叫做 b 子树。
具体过程就是：
- 对于根节点的值，如果根节点的值小于 x，那么左子树和根节点都是 a 子树，划痕（红线）就在右边，我们就向右子树递归；反之，划痕就在左边，向左子树递归。
- 整个函数返回的就是当前这个子树分裂出来的两个子树的根，如果是空树，那么根就是 0。前一棵子树属于a树，后一棵属于 b 树。递归返回之后，就将属于当前子树的根接到对应根的上面。由于更新了节点，所以我们要更新当前根节点的子树大小。返回当前跟和剩下的一棵树。
如果还不懂，我们用图片来演示，x=4:
这是一棵平衡树，因为根节点的值大于 x，所以我们向左递归。
此时分裂成两棵子树，右上方的那一个忽略，因为其所有的点都大于 x,不再需要进行操作。
左子树的根节点的值小于 x，所以分裂其右子树，向右递归。
同样的，由于右边的子树的根节点大于等于 x，所以向左递归。
左子树小于x，应该向右子树递归。
但是到了其右子树，树根为 x，即为空树，直接 \mathtt{return\ (0,0)}，代表P都没返回返回了两个空树。
返回后我们要将一颗树接到另一个一棵树上。
其实这张图片之前应该还有一张值为 3 的点与空子树合并^{[2]}的，但是因为没什么好说的。。。
因为值为 3 的根同根值为 2 的根一样都小于 x，所以它们合并。
如何确保合并后是一棵二叉搜索树呢？
显然，值为 3 的根的子树是在 2 的右子树分裂的，所以都保证大于等于 2。
返回值为 $2$ , $4$ 两个的根，因为值为 $5$ 的根大于 $x$,所以 $4$ 合并到 $5$ 的子树中。
至此，递归完毕，模拟结束，当然，在分裂后合并到子树的过程中，记得更新子树大小。
开始上代码。
因为要返回两个根，所以我们定义一个结构体。
```cpp
struct zyq{
int a,b;
zyq(int a_=0,int b_=0){//这样写可以让返回的更加自然
a=a_;b=b_;
}
};
```
然后新建一个结构体，讲平衡树的函数写在结构体中，这样可以方便调用~~装逼用~~。
```cpp
struct FHQ_Treap{
yyy a[maxn];int root,cnt;//root代表根节点，cnt代表最大的数组下标
}
```
写更新子树大小操作
```cpp
struct FHQ_Treap{
inline void Pushup(int k){
a[k].size=a[a[k].ls].size+a[a[k].rs].size+1;
}
}
```
根据我们上边的思路和模拟，给出分裂split的代码：
```cpp
struct FHQ_Treap{
inline zyq split(int k,int x){
if (!k) return zyq(0,0);
if (a[k].val<x){
zyq tmp=split(a[k].rs,x);
a[k].rs=tmp.a;
Pushup(k);
return zyq(k,tmp.b);
}
else{
zyq tmp=split(a[k].ls,x);
a[k].ls=tmp.b;
Pushup(k);
return zyq(tmp.a,k);
}
}
}
```
#### 合并 ( $merge$ )
合并什么呢，任意的两棵平衡树？
如果是任意的，那么复杂度将不能得到保证。所以同分裂操作一样，将一棵所有节点值小于等于另一棵平衡树的树合并。
```
struct FHQ_Treap{
inline int merge(int u,int v){//返回合并后的根。u是所有节点较小的一棵平衡树的根，v相反
}
}
```
还记得之前提到的节点值中有个叫做随机权的东西吗？ $\mathtt{Treap}$ 的平衡就是通过随机权来维护一个堆，保证它的平衡的。如果是来学平衡树的，应该都知道堆和其性质吧。根节点的随机权小于等于（或者大于等于，看个人喜好，本文中使用小根堆）左右节点的随机权。
所以合并的时候，因为左边子树的值已经小于等于右边子树的值了，所以我们只需维护堆的性质即可。
如果 $u$ 的随机权小于 $v$ 的随机权，就将 $u$ 的右节点作为根与 $v$ 合并，并更新子树大小；反之，就将 $v$ 的左节点作为根与 $u$ 合并，并更新子树大小。
因为合并比较节点， 这里就不给出详细过程了。
```cpp
struct FHQ_Treap{
inline int merge(int u,int v){
if (!u||!v) return u+v;
if (a[u].rnd<a[v].rnd){
a[u].rs=merge(a[u].rs,v);
Pushup(u);
return u;
}
else{
a[v].ls=merge(u,a[v].ls);
Pushup(v);
return v;
}
}
}
```
#### 插入
插入一个值为 $val$ 的节点。
将原来的平衡树分为小于 $val$ ，大于等于 $val$ 的两棵平衡树，然后新节点作根节点依次合并三棵平衡树即可。
```cpp
struct FHQ_Treap{
inline void insert(int val){
int k=++cnt;a[k].rnd=rand();a[k].size=1;a[k].val=val;
//初始化节点
zyq x=split(root,val);
root=merge(merge(x.a,k),x.b);
//写成merge(x.a,merge(k,x.b))也是可以的
//别忘记更新根节点
}
}
```
#### 删除
删除一个值为 $val$ 的节点。
讲原来的平衡树分为小于 $val$ ,等于 $val$ ,大于 $val$ 的三棵树。
将等于 $val$ 的这颗树的根节点的左儿子和右儿子进行合并，这样就相当于减少了一个节点。
接下来依次合并即可。
```cpp
struct FHQ_Treap{
inline void del(int val){
zyq x=split(root,val);
zyq y=split(x.b,val+1);
y.a=merge(a[y.a].ls,a[y.a].rs);
root=merge(x.a,merge(y.a,y.b));
}
}
```
#### 查询值为val的排名
非常简单，分成小于 $val$ ,大于等于 $val$ 的两棵树，查询小于 $val$ 树的子树大小，在外面加个 $1$ 即可。
别忘记把这两棵树合并回去。
```cpp
struct FHQ_Treap{
inline int rkdown(int val){
zyq x=split(root,val);
int ans=a[x.a].size;//我习惯在输出时加一
root=merge(x.a,x.b);
return ans;
}
}
```
#### 查询排名为x的数
虽然这次不能用 $split$ 和 $merge$ 函数来瞎搞了，但是我们可以重写一个函数。
思路也很简单，看代码理解吧。
```
struct FHQ_Treap{
inline int at(int x){
int k=root;
//从根节点开始查找
while (k){
if (x<=a[a[k].ls].size) k=a[k].ls;
//如果排名小于等于左子树的子树大小，就向左边走。
else if (x==a[a[k].ls].size+1) return a[k].val;
//如果等于当前节点，就直接输出
else x-=a[a[k].ls].size+1,k=a[k].rs;
//往右子树走的时候，别忘记讲x减去左子树的子树大小和根节点的大小
//因为K是要更新的，所以x和k更新的顺序不能颠倒（告诫后人，我在这当时调了好久）
//当然递归更好打，但是自从被FXTDL吐槽FHQ-Treap常数大以后，我就写非递归的了
}
}
}
```
#### 查询值为val的前驱
先找到 $val$ 的排名 $-1$ 设为 $x$ ，再找到排名为 $x$ 的数即可。
#### 查询值为val的后继
先找到 $val+1$ 的排名设为 $x$ ，再找到排名为 $x$ 的数即可。
#### 代码总览
```cpp
#include<bits/stdc++.h>
#define maxn 1100005
#define rg register
using namespace std;
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
struct yyy{
int ls,rs,val,rnd,size;
};
struct zyq{
int a,b;
zyq(int a_=0,int b_=0){
a=a_;b=b_;
}
};
struct FHQ_Treap{
yyy a[maxn];int root,cnt;
int seed=1;
inline void Pushup(int k){
a[k].size=a[a[k].ls].size+a[a[k].rs].size+1;
}
inline zyq split(int k,int x){
if (!k) return zyq(0,0);
if (a[k].val<x){
zyq tmp=split(a[k].rs,x);
a[k].rs=tmp.a;
Pushup(k);
return zyq(k,tmp.b);
}
else{
zyq tmp=split(a[k].ls,x);
a[k].ls=tmp.b;
Pushup(k);
return zyq(tmp.a,k);
}
}
inline int merge(int u,int v){
if (!u||!v) return u+v;
if (a[u].rnd<a[v].rnd){
a[u].rs=merge(a[u].rs,v);
Pushup(u);
return u;
}
else{
a[v].ls=merge(u,a[v].ls);
Pushup(v);
return v;
}
}
inline void insert(int val){
int k=++cnt;a[k].ls=a[k].rs=0;a[k].rnd=rand();a[k].size=1;a[k].val=val;zyq x;
x=split(root,val);
root=merge(merge(x.a,k),x.b);
}
inline void del(int val){
zyq x=split(root,val);
zyq y=split(x.b,val+1);
y.a=merge(a[y.a].ls,a[y.a].rs);
root=merge(x.a,merge(y.a,y.b));
}
inline int rkdown(int val){
zyq x=split(root,val);
int ans=a[x.a].size;
root=merge(x.a,x.b);
return ans;
}
inline int at(int x){
int k=root;
while (k){
if (x<=a[a[k].ls].size) k=a[k].ls;
else if (x==a[a[k].ls].size+1) return a[k].val;
else x-=a[a[k].ls].size+1,k=a[k].rs;
}
}
}f;
int main(){
srand(time(0));
rg int i,n,m,x,ans=0,last=0,op;
//freopen("1.in","r",stdin);
read(n);read(m);
while (n--) read(x),f.insert(x);
while (m--){
read(op);read(x);x^=last;
if (op==1) f.insert(x);
else if (op==2) f.del(x);
else{
if (op==3) last=f.rkdown(x)+1;//记得+1
else if (op==4) last=f.at(x);
else if (op==5) last=f.at(f.rkdown(x));
else last=f.at(f.rkdown(x+1)+1);//记得+1
ans^=last;
//printf("%d %d\n",last,f.root);
}
}
printf("%d ",ans);
return 0;
}
```
### 复杂度
空间复杂度显然是线性的，比权值线段树好。
但是由于是按照随机权维护平衡的，所以这个时间复杂度**期望**为 $O(n\log{n})$，所以在有些时候不如 $\mathtt{splay}$ 等平衡树。
~~如果你是非酋的话复杂度就是~~$O(n^2)$~~的~~。
### 为什么选择FHQ-Treap
以下是我的理由：
1. 我一开始学习的是替罪羊树，但是由于不能实现区间操作，打了一段时间后便学习了 $\mathtt{FHQ-Treap}$。当然替罪羊树作为入门平衡树是非常好的选择（ $\mathtt{Treap}$ 也是）。
2. $\mathtt{FHQ-Treap}$ 码量较与 $\mathtt{splay} $ 来说，是少了很多的，所以常数也对应少了一点（暴论）。
3. $\mathtt{FHQ-Treap}$ 可以实现线段树的功能，也可以实现普通的权值平衡树，文艺平衡树以及两种平衡树的可持久化。这是仅仅这一种平衡树可以同时实现这么多功能的。
## 2. 区间信息维护
说人话，就是可以在一些时候代替线段树的东西。
但是也可以完成一些线段树不能完成的东西，比如文艺平衡树。
### 区间和
好的我们先看到[线段树1](https://www.luogu.com.cn/problem/P3372)。
这题十分简单，但是为了从权值平衡树过渡到区间信息维护的平衡树，还是讲一讲。
这时候这颗平衡树的中序遍历不是每个节点的值从小到大排列，而是这个序列的排列。
我们把这个平衡树想象成一棵线段树，线段树的精髓是什么——下传标记 $\mathtt{Pushdown}$。所以说，我们在 $\mathtt{split}$ 和 $\mathtt{merge}$ 的操作之前下传标记（这样不会影响其他节点）。回溯的时候更新 $\mathtt{Pushup}$ 就好了，如果线段树打熟悉了自然也懂。
怎么查询呢？有一种十分~~暴力~~简单的方法，就是将一棵平衡树分裂成三棵 $[1 ,l-1]$,$[l,r]$,$[l+1,r]$ 三棵平衡树（如果 $l=1$ 或者 $r=n$ 那么就是两棵或者一棵）。然后暴力查询根节点的信息。所以说，每个根节点就是要维护整棵子树的信息。
非常简单，就是分裂的时候代码略有不同，看注释吧。
```cpp
#include<bits/stdc++.h>
#define maxn 100005
#define rg register
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
inline void readl(long long &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
struct yyy{
int ls,rs,size,rnd;
long long val,lazy,sum;//记得开long long
}a[maxn];
int root,cnt;
inline void cover(int k,int x){
a[k].val+=x;
a[k].sum+=x*a[k].size;
a[k].lazy+=x;
}
inline void Pushdown(int k){
if (a[k].lazy){
if (a[k].ls) cover(a[k].ls,a[k].lazy);
if (a[k].rs) cover(a[k].rs,a[k].lazy);
a[k].lazy=0;
}
}
inline void Pushup(int k){
a[k].size=a[a[k].ls].size+a[a[k].rs].size+1;
a[k].sum=a[a[k].ls].sum+a[a[k].rs].sum+a[k].val;
}
inline void split(int k,int x,int &a_,int &b_){//因为每次回传结构体很慢，所以说这种写法要好一些
if (!k) a_=b_=0;
else{
Pushdown(k);//在递归开始前进行下传标记
if (a[a[k].ls].size+1<x){split(a[k].rs,x-a[a[k].ls].size-1,a[k].rs,b_);a_=k;}
//x记得减去左边的子树和当前节点的大小
else {split(a[k].ls,x,a_,a[k].ls);b_=k;}
Pushup(k);
}
}
inline int merge(int u,int v){
if (!u||!v) return u|v;
if (a[u].rnd<a[v].rnd){
Pushdown(u);
a[u].rs=merge(a[u].rs,v);
Pushup(u);
return u;
}
else{
Pushdown(v);
a[v].ls=merge(u,a[v].ls);
Pushup(v);
return v;
}
}
inline int clone(long long val){
a[++cnt].val=val;a[cnt].sum=val;
a[cnt].size=1;a[cnt].rnd=rand();
return cnt;
}
long long g[maxn];
inline int Build(int l,int r){
if (l==r) return clone(g[l]);
int m=l+r>>1;
return merge(Build(l,m),Build(m+1,r));
}//均摊建树
int main(){
// freopen("1.in","r",stdin);
srand(51569);
rg int tmp1,tmp2,tmp3,i,n,m,op,l,r;rg long long x;
read(n);read(m);
for (i=1;i<=n;i++) readl(g[i]);
root=Build(1,n);
while (m--){
read(op);read(l);read(r);
if (op==1){
readl(x);
split(root,l,tmp1,tmp2);
split(tmp2,r-l+2,tmp2,tmp3);//因为是按子树大小分裂，所以说这里的x应该是当前序列的。
cover(tmp2,x);
root=merge(tmp1,merge(tmp2,tmp3));
//记得合并
}
else{
split(root,l,tmp1,tmp2);
split(tmp2,r-l+2,tmp2,tmp3);
printf("%lld\n",a[tmp2].sum);
root=merge(tmp1,merge(tmp2,tmp3));
}
}
return 0;
}
```
对于这道题以及一些线段树题，不推荐大家使用FHQ-Treap，我在这里只是做一个演示~~装B~~以及更好的理解文艺平衡树。FHQ-Treap是期望复杂度而且常数大的跟*一样。~~线段树真香~~。
~~我不会告诉你我加了快读最慢的一个点跑了500ms~~。