FHQ Treap
FHQ Treap
简介
FHQ Treap是一棵利用分裂和合并实现插入，删除，查询操作的平衡树。
先提一嘴：所有平衡树的基础操作都能通过合并与分裂实现，所以先实现这两个看似与平衡树无关的操作是必要的，它们的重要性就像其它平衡树的 rotate 。
分裂
我们需要将一棵 BST 分成两棵，一棵中的每个节点的权值小于等于数字 \(k\) ，另一棵中每个节点的权值都要比数字 \(k\) 大。
为了方便，我们不妨把节点权值小的那棵树叫做小树，另一棵叫做大树。
怎么实现呢？
我们想，当我们遇到一个节点时，它的权值可能有两种情况：
- 小于等于 \(k\) 。
- 大于 \(k\) 。
如果我们遇到的节点小于等于 \(k\) ，根据 BST 性质，它的左子树中的所有节点，权值一定都小于等于 \(k\) 。
所以呢？
统统丢进我们的小树里就好啦~
那如果大于呢？
把它的右子树统统丢进我们的大树里就好啦~
然后呢？
递归一直丢，丢到叶子节点就好啦~
怎么丢？
我也不知道啦~
咳咳，我们可以先整理一下刚才的成果，无非就下面一句话：
小进小，递归右；大进大，递归左。
意思就是：
如果当前节点的权值是小过 \(k\) 的，进小树，然后递归右子树，反之同理。
那么：
如果当前节点权值小过 \(k\) ，我们的小树当前的左子树就是当前节点的左子树，差右子树没接，同时我们往右递归。
所以接下来，我们再要接小树时，应该接到当前节点的右儿子位置上。
同理，如果当前节点权值大过 \(k\) ，我们接下来如果要接大树时，就要接在当前节点的左儿子位置上？
知道这个有什么用呢？
我们可以粗略考虑像下面这样完成分裂。
（ now 表示当前节点， x 表示接小树该接的地方， y 表示接大树该接的地方， ls 指代左儿子， rs 指代右儿子， val[] 为记录每个节点权值的数组 ）
void split(int now,int k,int &x,int &y)
{
if (val[now]<=k) x=now,split(rs[now],k,rs[now],y);
else y=now,split(ls[now],k,x,ls[now]);
}
这里的 x=now , y=now ，就是前面所说的：
小进小；大进大。
后面的就是：
递归左；递归右。
不过我们为了完成接下来的操作，我们还要记录每个节点的子树，这需要我们在分裂合并时更新。
inline void update(int x) { siz[x]=siz[ls[x]]+siz[rs[x]]+1; }
我们还要为递归加上边界，所以最后的分裂代码是这样的：
void split(int now,int k,int &x,int &y)
{
if (!now) x=y=0;
else
{
if (val[now]<=k) x=now,split(rs[now],k,rs[now],y);
else y=now,split(ls[now],k,x,ls[now]);
update(now);
}
}
合并
顾名思义，合并就是将两棵 BST 合并为 一棵 BST 。特别的是，因为我们在 split 操作中严格规定了哪棵树中的节点更大，所以在合并时我们也可以利用这一点，传递变量时保护好这个性质，这样我们合并时就只用比较 rd 值的大小了。
rd 是什么？
因为 FHQ Treap 是一棵 Treap ，所以它维持平衡的原理是让每个节点带上一个随机值，在维护权值 BST 性质的同时维护随机值的堆性质，形成一棵笛卡尔树，因为堆键值是随机的，所以期望高度为 \(\log n\) 。
像是下面这样：
void merge(int x,int y)
{
if (rd[x]上面这段代码已经能够概括合并的思路了，但是有细节上的问题：
- 我们在合并时改变了 BST 的结构，所以需要重新维护
siz的大小。 - 这样的合并是成功了，但是我们也丢失了新树的根，会为下一次的分裂操作带来麻烦。
- 我们没有设置递归边界。
所以我们对其进行修改：
int merge(int x,int y)
{
if (!x||!y) return x+y;
if (rd[x]其中的 if (!x||!y) return x+y; 表示若二者之一为 \(0\) ，返回另一者，即递归边界。
第 \(k\) 大数
这个操作其实与后面的 num() 目的相同，即求 BST 中第 \(k\) 大的数，但因为可以用于求前驱后继，所以先单独拎出来写。
kth() 的原理非常简单，这得益于我们之前费力维护的 siz 数组，它将在这个环节大显身手。
如果当前节点的 siz 大过 \(k\) ，向左子树递归；
如果当前节点的 siz 等于 \(k-1\) ，那答案就是当前节点；
否则当前节点的 siz 一定小于 \(k-1\) ，将 \(k\) 减去左子树的 siz ，再减去 \(1\) （ 即当前节点 ），向右子树递归。
代码如下：
inline int kth(int now,int k)
{
while (1)
if (k<=siz[ls[now]]) now=ls[now];
else if (k==siz[ls[now]]+1) return now;
else k-=siz[ls[now]]+1,now=rs[now];
}
插入
终于进入到平衡树所需要完成的操作了，接下来的方便一定会让你感到之前的努力没有白费。
因为我们已经能够将一棵 BST 分裂，所以插入一个点时，直接新建这个点，让原来的树沿着这个点的权值裂开，再将左右子树与这个点合并即可。
我们不妨顺手写一个新建节点的函数，这是我们最后的准备了：
inline int create(int x)
{
siz[++tot]=1;
val[tot]=x;
rd[tot]=rand();
return tot;
}
那么插入操作的代码如下：
inline void ins(int k)
{
split(root,k,x,y);
root=merge(merge(x,create(k)),y);
}
删除
有了分裂操作，删除也是易如反掌。
我们直接将需要删除的节点的两边裂开，把中间的节点 ”取走“ ，再把裂出来的两棵树合并回来就好。
代码如下：
inline void del(int k)
{
split(root,k,x,z);
split(x,k-1,x,y);
y=merge(ls[y],rs[y]);
root=merge(merge(x,y),z);
}
查询排名
因为我们处理了 siz 数组，所以一个数的排名就等于比它小的节点构成的树的大小，我们同样可以用 split() 完成这项工作。
代码如下：
inline void rank(int k)
{
split(root,k-1,x,y);
printf("%d\n",siz[x]+1);
root=merge(x,y);
}
查询第 \(k\) 大数
这不就是我们刚才写的 kth() 嘛，摆上摆上。
代码如下：
inline void num(int k) { printf("%d\n",val[kth(root,k)]); }
前驱
求前驱，相当于求比这个节点权值小的节点构成的树（ 小树 ）中的权值最大节点，说起来有点绕，上码。
代码如下：
inline void last(int k)
{
split(root,k-1,x,y);
printf("%d\n",val[kth(x,siz[x])]);
root=merge(x,y);
}
后继
与求前驱类似，求后继就是求比这个节点权值大的节点构成的树（ 大树 ）中的权值最小节点。
代码如下：
inline void next(int k)
{
split(root,k,x,y);
printf("%d\n",val[kth(y,1)]);
root=merge(x,y);
}
Code
P3369 【模板】普通平衡树
#include
#include
#include
using namespace std;
#define MAXN (int)(1e5+233)
int n,opt,in;
int tot,root,x,y,z;
int ls[MAXN],rs[MAXN],val[MAXN],rd[MAXN],siz[MAXN];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f*x;
}
inline void update(int x) { siz[x]=siz[ls[x]]+siz[rs[x]]+1; }
inline int create(int x)
{
siz[++tot]=1;
val[tot]=x;
rd[tot]=rand();
return tot;
}
void split(int now,int k,int &x,int &y)
{
if (!now) x=y=0;
else
{
if (val[now]<=k) x=now,split(rs[now],k,rs[now],y);
else y=now,split(ls[now],k,x,ls[now]);
update(now);
}
}
int merge(int x,int y)
{
if (!x||!y) return x+y;
if (rd[x] 区间翻转
平衡树还能实现一种操作，就是维护一个有序序列，支持对一个区间内的元素进行区间翻转。
因为我们维护的是节点的顺序，而不是节点的大小排序，所以我们在分裂时并不用考虑节点的权值大小，而是考虑节点的排名。
相对应，原来的分裂方式我们称为权值分裂，而现在的分裂方式我们称为排名分裂。
void split(int now,int k,int &x,int &y)
{
if (!now) { x=y=0; return; }
if (tag[now]) pushdown(now);
if (siz[ls[now]]如上，我们在分裂时比较的关键字由节点权值变为节点排名。因为要支持翻转，所以我们要同时维护一个 lazy_tag 。
那么翻转操作也就很简单了。无非就是把要改的那棵子树拉出来，根打上 tag ，再塞回去。（ 好恶心口区 ）
inline void reverse(int l,int r)
{
split(root,l-1,x,y);
split(y,r-l+1,y,z);
tag[y]^=1;
root=merge(x,merge(y,z));
}
模板：P3391 【模板】文艺平衡树
#include
#include
#include
using namespace std;
#define MAXN (int)(1e5+233)
int n,m,l,r;
int tot,root,x,y,z;
int ls[MAXN],rs[MAXN],val[MAXN],rd[MAXN],siz[MAXN];
bool tag[MAXN];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f*x;
}
inline void swap(int &x,int &y) { int t=x;x=y,y=t; }
inline void update(int x) { siz[x]=siz[ls[x]]+siz[rs[x]]+1; }
void pushdown(int x)
{
swap(ls[x],rs[x]);
if (ls[x]) tag[ls[x]]^=1;
if (rs[x]) tag[rs[x]]^=1;
tag[x]=0;
}
inline int create(int x)
{
siz[++tot]=1;
val[tot]=x;
rd[tot]=rand();
return tot;
}
void split(int now,int k,int &x,int &y)
{
if (!now) { x=y=0; return; }
if (tag[now]) pushdown(now);
if (siz[ls[now]]