FHQ-Treap
学习这种平衡树不需要了解 treap，据说 treap 和 splay 能干的事情他也能干。
update：2023.1.12 以前写的博客看起来太仓促了，修改了一下。
前置芝士
二叉搜索树的性质。
二叉堆。
二叉搜索树
二叉搜索树就不细讲了，这里只简单说一下他的一个重要性质：左子树的点的值都小于根节点的值，右子树的点的值都大于根节点的值，且左右子树都满足这个性质（可能有点抽象，可以自行百度一下来理解一下，只要性质明白了就好）。
堆
这个就不讲了自行百度一下吧咕咕咕。
FHQ的两大基本函数
FHQ之所以 nb 就是因为他不跟隔壁 treap 一样需要旋转，而是用一种非常暴力的手段——分裂与合并。
基本上所有的操作都是依靠这两个函数的操作完成的。
而FHQ和treap一样，需要用到随机函数给每一个点一个随机附加权值来在合并时维护堆的性质，只要脸不是特别黑，他都能保持一个较为平衡的状态。
先来些定义方便下面理解。
int ch[N][2];//ch存放每一个节点的左右儿子编号
int val[N];//val存放每一个点的权值
int siz[N];//siz存放每一个节点的树的大小
int rad[N];//rad存放附加权值
int cnt;//cnt是计数器
int t,op;//t是操作的个数
int x,y,z;//xyz都是分裂出来的子树根节点的编号
int a,root=0;//root是树根，a是一个工具变量
前置小函数：
inline void p_p(int x)//更新节点的siz大小
{siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}//更新
inline int node(int x)//新开一个点
{
siz[++cnt]=1;//赋初值，一开始只有他本身一个点
val[cnt]=x;//赋权值
rad[cnt]=rand();//赋随机附加权值
return cnt;//返回当前节点的编号
}
注意：以下的图片中点的权值等于序号的值
分裂
先把代码放出来，不然不好理解
inline void split(int now,int k,int &x,int &y)//分裂操作，xy是分裂出来的两棵树的根节点编号
{
if(!now)x=y=0;
else
{
if(val[now]<=k)
x=now,split(ch[now][1],k,ch[now][1],y);
else
y=now,split(ch[now][0],k,x,ch[now][0]);
p_p(now);
}
return 0;
}
一开始的 xy 是空的，要注意 xy 前面是有取地址符的，接下来我们慢慢模拟。
假如说我要以权值为4分裂
从根节点开始遍历，6大于4是 y 树的节点，并且他的右子树的点的权值也一定是大于4的，所以他的右子树也都属于 y 树（二叉搜索树的性质），当前 y 指向6，继续向6的左子树搜
红色的是 y 树的节点，蓝色的是 x 树的节点
然后我们来到了4，4等于4应该在 x 树里面，同理他的左子树也都属于 x 树，这时我们 y 不变，x 指向4，继续寻找当前点的右子树
- 当前已经出来了 x y 树的根节点
然后我们就来到了5，5大于4应该在 y 树里面，此时x不变，y指向了5，之前y指向的是6，往下递归的时候把 y 给传成了6的左儿子，所以他俩之间就相当于建了一条边，也就是说现在5成了6的左儿子，继续往5的左子树搜
此时发现没有左子树，也就是 now 等于0，所以此时把 x y 清空并返回上一层递归，这时应该就可以发现，已经分完了。
第一个返回 xy 的值肯定是分出来的两棵树的根节点，因为再往后递归分裂的话就是某一个点的左右儿子下标了；而在往下递归的过程中，没有因为没有当前点而清空 xy 的都像上面的6和5一样建边形成了一棵完整的树。
- 分裂完成的树的效果图在下面
合并
先来代码：
inline int merge(int x,int y)//合并函数，返回值是合并后的根节点编号
{
if(!x||!y)return x+y;//如果x为空返回y，y为空就返回x
if(rad[x]<rad[y])//维护堆的性质，如果x的优先级小于y的优先级
{
ch[x][1]=merge(ch[x][1],y);//y就往x的右子树里面插
p_p(x);//更新当前x树的siz
return x;//返回是以x为根
}
else
{
ch[y][0]=merge(x,ch[y][0]);//把x往y的左子树里面插
p_p(y);//更新y点的siz值
return y;//返回以y为根
}
}
以刚刚分裂出来的树为例，对了标一下用的到的随机权值
我现在要把他俩合并起来
比较4和6的优先级（随机权值），6比4的优先级要高，所以把4往6的左子树里面插，这样才能维护堆的性质。
现在来比较4和5的大小，4比5的优先级高，所以我们把5往4的右子树里面插
现在发现4没有右子树，所以直接返回以5为根到上一层递归，然后5就接到了4的右子树上，更新节点的值后返回以4为根到上一层递归，此时4就又成了6的左儿子，至此合并完成。
进阶操作
插入一个数
插入一个数需要按 k 的值给分裂成两棵树，然后给 k 新开一个点，把 x 和 k 合并，再把 x 和 y 合并就好了。
代码如下：
split(root,a,x,y);//先按a把树分裂
root=merge(merge(x,node(a)),y);//然后把a开一个点，和x合并后在与y合并返回新的树根
删除一个数
删除一个数的话需要把原来的树分成三棵树，小于 k 的一棵树，等于 k 的一棵树，大于 k 的一棵树，然后把等于 k 的那棵树给左右儿子一合并掉，吞掉根节点，然后在把树合并成一棵就好了。
代码如下：
split(root,a,x,z);//按a把树分裂成xz两个子树
split(x,a-1,x,y);//按照a-1把子树x分裂成xy两个子树，此时y子树的点都是等于a的
y=merge(ch[y][0],ch[y][1]);//删掉根节点，合并左右子树
root=merge(merge(x,y),z);//然后把所有的子树都合并起来
根据值查找排名
把小于 k 的都给分裂出来，然后输出他的大小加一即可。
代码如下：
split(root,a-1,x,y);//按a-1分裂成xy两个子树
cout<<siz[x]+1<<endl;//输出当前点的排名
root=merge(x,y);//合并取出新根节点编号
根据排名查找值
很遗憾，这个操作只能和 treap 一样，代码如下：
inline int kth(int now,int k)//查询第k大的数
{
while(1)
{
if(k<=siz[ch[now][0]])//如果k比当前节点的左子树小
now=ch[now][0];//now就替换成左子树的根节点
else
{
if(k==siz[ch[now][0]]+1)//如果k等于当前节点的左子树大小加1
return now;//直接返回当前节点的值
else//否则
k-=siz[ch[now][0]]+1,now=ch[now][1];//k减去当前点左子树的大小加一，继续去右子树查询
}
}
}
查找前驱
把小于 k 的都分裂出来然后从里面找一个最大值即可，代码如下：
split(root,a-1,x,y);//按照a-1把树分裂为xy两个子树
cout<<val[kth(x,siz[x])]<<endl;//输出x子树中的最大值
root=merge(x,y);//然后把xy两个子树合并起来
查找后继
把大于 k 的都分裂出来然后从里面找一个最小值即可，代码如下：
split(root,a,x,y);//按照a把树分裂为xy两个子树
cout<<val[kth(y,1)]<<endl;//输出y子树中比x大的最小的值
root=merge(x,y);//然后把两个子树合并起来
好的以后有空再来更新。
标签：int,root,笔记,treap,分裂,xy,权值,FHQ,节点 From： https://www.cnblogs.com/Multitree/p/16674038.html