模板传送FHQ-Treap顾名思义就是范浩强大佬设计的一种二叉平衡树下面我们来讲一下它的原理和代码
(相关资料图)
对于一个节点，我们需要记录的是
对应的值子树节点数左右孩子编号对应的随机值struct str{int val,size,l,r,key;}fhq[100005];看到这里有人疑惑了，这个对应的随机值是怎么回事啊？这里就涉及到了一个FHQ-Treap里优化的一个小技巧我们知道，树在最坏的情况下，会退化成一条链但很显然，出于时间复杂度上来讲，我们并不希望它成为一条链，因为我们的遍历是按照一层一层来遍历的，如果退化成一条链就会从最优O（log n）的复杂度直接降到O( n )，所以我们就用这个随机的值去让这个二叉树变得平衡，具体怎么去使用这个随机值的请看函数merge
函数首先，先给大家把主要使用的函数列出来，然后我们再一个一个讲
void update(int x)void split(int now,int dat,int &x,int &y)int merge(int x,int y)int add(int dat)void ins(int dat)void del(int dat)int get_rk(int dat)int get_num(int dat)void get_pre(int dat)void get_next(int dat)看起来是不是很让人头晕眼花？我们把函数要具体实现什么注释一下：
void update(int x)//更新数据void split(int now,int dat,int &x,int &y)//分裂int merge(int x,int y)//合并int add(int dat)//在树里添加节点（实际的操作）void ins(int dat)//节点进树（与上一个要区分开，这个只是一个输入的对接）void del(int dat)//节点出树int get_rk(int dat)//求dat数的排名int get_num(int dat)//求排dat名的数void get_pre(int dat)//求前驱void get_next(int dat)//求后继铺垫的差不多了，是时候开始讲了
updateupdate函数十分简单，主要要求实现的是更新该节点的子树长度，因为我们会在树上进行其他的修改操作，长度很可能会随之变化，所以这个函数一定是要放在第一位写的
void update(int x){//要更新x节点fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1; //子树节点数=左子树节点数+右子树节点数+本身；return ;}这个函数是FHQ-Treap的重点之一，主要实现的是把一棵树拆成两棵树方便后续操作，我们先解释一下这里的参数都是什么意思
void split(int now,int dat,int &x,int &y)//now表示现在遍历到了哪个节点，dat是要从哪里拆开这棵树，x和y是拆后两颗树的根节点因为x和y的值在函数里会被不停地更新，所以我们这里的&x，&y就尤为重要第一步，根据二叉搜索树，找到从哪里分成两半
if(dat（如果看不懂的话可以自己画个图理解一下，本人能力有限，不会做动图）最后，我们就会把分裂出来的两棵树的根节点求出来你以为这样就完了吗？还要注意几个细节：递归跳出：
if(now==0){x=y=0;return ;}还有！你已经修改了这棵树了，别忘了更新！！！
update(now);来到第二个重点，也是有很多人包括刚学的我非常不理解的地方————合并函数还是先解释参数
int merge(int x,int y)//将以x为根的树和以y为根的树合并它到底是怎么用这些随机值来保持平衡的呢？我们来看一个问题：现在你有两棵二叉搜索树，并且告诉你一棵树的根节点x一定比另一颗树的根节点y要小，请问你能怎么组合？聪明的你肯定会想到两种情况：
第一种是把x插进y的左子树里，第二种是把y插进x的右子树里如果把这个问题交给聪明的你的话，你一定会选择尽可能平衡的一种做法来合并，但很可惜，计算机并没有你那么聪明的脑子，它只会机械的执行一种操作，而这种操作执行下去就会逐渐变成一条链，怎么办呢？这时候我们的随机值就发挥出用场了，当面对于这样的两难抉择中，它就不会再去考虑x和y的值，不会去考虑这棵二叉平衡树（因为很显然，前者没必要，给你的时候就知道x小y大，后者不用管，因为怎样操作都是一棵二叉平衡树），而是去维护堆
注意！我在这里是维护的小根堆！如果我们x的key要小于y的key的话，根据小根堆我们就要把它合并到y的左子树中如果我们y的key要小于x的key的话，根据小根堆我们就要把它合并到x的右子树中（强迫症满意地笑了）这样，我们就通过这些小小的随机值完美的解决了这个难题，维护了二叉搜索树的平衡代码如下
if(fhq[x].key<=fhq[y].key){fhq[x].r=merge(fhq[x].r,y);//y插进x的右子树update(x);//别忘更新！我爱更新！警钟长鸣！这个代码第一次的bug就是忘更新了return x;//返回的是合并后的根节点}else{fhq[y].l=merge(x,fhq[y].l);//x插进y的左子树update(y);//别忘更新！我爱更新！return y;}别忘了递归的跳出~
if(x==0||y==0) return x+y;这个函数相较于上两个来说就简单了还是参数
int add(int dat)//添加一个值为dat的节点，返回该节点下标我们只需要给它进行以下操作
fhq[++cnt].size=1;//cnt是这棵树的总节点数fhq[cnt].key=rand(); //取随机值fhq[cnt].val=dat;return cnt;OK力~
ins解释参数
void ins(int dat)//插入一个dat进树这里就很好玩了，我们的操作是这样先通过dat值把这棵树劈成两半，此时一半<=dat，一半>dat
split(root,dat,x,y);//root是这棵树的根传回来了两棵树的根节点后，我们把这个节点先悄悄的加进树里，此时相当于有三棵树存在
z=add(dat);然后呢，我们要当老六，把这三棵树再组成一棵树
root=merge(merge(x,z),y);这样，我们的添加节点操作就不可思议而且妙不可言的完成了！
del与上一个函数相反，这个函数是删除操作
void del(int dat)//删除值为dat的一个节点这个操作也很妙，集中注意力我们先通过dat值把这棵树劈成两半，此时一半<=dat，一半>dat
split(root,dat,x,y);然后和上面的思想差不多，我们再从<=dat的左树中再劈成两半，一半是=dat的节点，一半是其他节点
split(x,dat-1,x,z);//从左树根节点开始通过dat-1把左树劈成一半<=dat-1,一半=dat然后呢，我们再把这个左树中的其他节点与右树一合并，一个dat就自然而然的被排挤出去了！
z=merge(fhq[z].l,fhq[z].r);//这里是重点！！！我们只需要删除一个dat而剩下的dat还是要再加回树里的！root=merge(merge(x,z),y);//三块合并这样这个操作也完成啦~
get_rk这个函数是用来求值为dat的数的排名的操作比上两个还要简单，我们通过dat值把这棵树劈成两半，此时一半<=dat，一半>dat，然后我们直接把左子树的节点数+1就是dat数的排名了~
split(root,dat-1,x,y);int ans=fhq[x].size+1;merge(x,y);//分裂完别忘了合并！return ans;这个函数的作用是求排名为dat的数值是多少还是分类讨论的思想，我们发现这个排dat名的数要么在当前节点的左子树上，要么在当前节点的右子树上，要么就是当前节点，然后我们就可以写一个递归或循环来解决问题了（本人懒得写递归了，如果有递归强迫症可以自己写一下）
int now=root;//当前遍历到了哪个节点while(now){ if(fhq[fhq[now].l].size+1==dat){//就是当前节点 break;}else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;//在左子树里else{//在右子树里dat-=fhq[fhq[now].l].size+1;//注意！右子树比左子树都要大！所以求的时候一定要把左子树节点数减掉！now=fhq[now].r;}}return fhq[now].val;//华丽返回~这样就又ok了
get_pre一个求dat前驱的函数，操作起来也很妙我们先通过dat-1把这棵树劈成两半，此时一半
split(root,dat-1,x,y);int now=x;while(fhq[now].r) now=fhq[now].r;//找左子树中最大的那一个，一定是最右的节点cout<与上面的思想相同，但是这回我们要在右子树中找这个值：我们先通过dat把这棵树劈成两半，此时一半<=dat，一半>dat然后我们就会发现，右子树中最大的那一个，就是dat的后继
split(root,dat,x,y);int now=y;while(fhq[now].l) now=fhq[now].l;//找右子树中最小的那一个，一定是最左的节点cout<这样，我们就把所有的函数都捋了一遍，主函数也就好写了，以下是完整的AC代码
#include#include#include#include#include#include#include//这个里面有rand函数，必须写！using namespace std;int n;int cnt;int root;struct str{int val,key,size,l,r;}fhq[100005];void update(int x){fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;return ;}void split(int now,int dat,int &x,int &y){//分裂 if(now==0){x=y=0;return ;}if(dat=dat)now=fhq[now].l;else{dat-=fhq[fhq[now].l].size+1;now=fhq[now].r;}}return fhq[now].val;}void get_pre(int dat){//求前驱 int x,y,z; split(root,dat-1,x,y);int now=x;while(fhq[now].r) now=fhq[now].r;cout<>n;while(n--){int opt,x;cin>>opt>>x;if(opt==1) ins(x);else if(opt==2) del(x);else if(opt==3) cout< 好了，看到这里，想必你已经掌握了FHQ-Treap了，我们在下一个平衡树相见吧！
标签：
