平衡树中的神级数据结构----> FHQ-Treap！

在食用本文前，需要有一个必备前置知识：简单的Treap的原理，然后便可以愉快地食用该文章了

通过极其痛苦的学习，终于入门了数据结构–平衡树，同时由于Splay,Treap,BST等均可在网上查阅到适合自己的讲解，但对于FHQ-Treap，我觉得更加有趣，所以写下这篇简述。

FHQ-Treap简介

FHQ-Treap是由大神FHQ发明的，一种不用旋转的Treap，代码复杂度不高，并且可以实现Splay与Treap的全部功能。！但是在处理LCT问题上并没有Splay效率高，但好像在其他问题的处理上FHQ-Treap的效率似乎更高一点？

言归正传，FHQ-Treap为什么可以做到无旋呢？原因便是其中的两个核心的操作函数，merge与split。下面将用通俗的语句对这两种操作进行讲述，如果出现专业性错误，还请斧正。

首先介绍split操作,先贴代码吧，这样对着文字看或许有助于理解。

void split(int p,int key,int &x,int &y)
{
    if(!p) 
    {
        x=y=0;
        return;
    }
    else
    {
        if(tr[p].key <= key)
            x=p,split(tr[p].r,key,tr[p].r,y);
        else
            y=p,split(tr[p].l,key,x,tr[p].l);
    }
    pushup(p);
}

split操作，便是将根节点为p的树拆分为根节点为x的树，和根节点为y的树，首先介绍一下传入的参数，p为要分割的树的根节点，x，y分别为分割后的两棵树的根节点。split分割的关键字分为两种，一种为按权值划分（即本文中介绍的方式），另一种是按维护堆的性质按随机val进行划分。上述代码为按照某一特定值进行划分。即传入的第二个参数为key。

代码解读

如果当前树没有子节点，那么将x，y置成0并返回即可，如果当前节点值小于目标值，那么就将其划分至树x，由于根节点都满足条件，相应的左子树上的点遍都满足条件，所以只需要递归搜索右子树即可，满足条件保留在右子树，不满足的划分至树y即可。同理便可理解剩余代码。最后将题目中需要维护的信息进行更新（pushup操作）即可，当然也可能不需要。

接下来介绍merge操作,依旧先贴代码在进行解读。

int merge(int x,int y)
{
    if(!x or !y) return x+y;
    if(tr[x].val > tr[y].val)
    {   
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else
    {
        tr[y].l=merge(x,tr[y].l);
        pushup(x);
        return x;
    }
}

merge操作，便是将根节点为x与根节点为y的树进行合并。所以传入的参数便是需要合并的两棵树的根节点，返回值是合并成一棵树后的根节点。

代码解读

如果其中一棵树是空的，那么直接返回x+y即可。否则如果x树的val大于y树的val那么x应该在y的左上方，即递归将y与x树的右子树合并即可，合并后更新节点信息，并返回根x，同理即可理解后半部分代码。tip：（val是与Treap原理相同的一个随机值，只用来维护树的平衡，保证其不会退化成一条链，即操作期望复杂度为log（n））

介绍完上述两个核心操作后，对于pushup与get_node基本操作，均与普通Treap区别不大，贴一下本人的代码，仅供参考！

void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
}

int get_node(int c)
{
    tr[++idx].key=c;
    tr[idx].val=rand();
    tr[idx].size=1;
    return idx;
}

到这里其实对于FHQ-Treap中所涉及到的基本函数已经都写完了，剩下的操作，均是有以上四个函数组合出来的。（数组翻转等需要lazy标记操作除外，其实加个pushdown改一改就行了）。所以接下来将以平衡树模板题为例，进行讲述。https://www.acwing.com/problem/content/255/

在此题中涉及到以下6个操作分别为：1、插入某个数（insert），2、删除某个数（dele），3、查询数x的排名（getrank），4、查询排名为x的数（getnum），5、求某个数的前驱（getlast），6、求某个数的后继（getnext）。tip:括号为本人代码中函数的命名，仅供参考。

接下来分别讲解上述6个操作的实现方法与原理

1、插入一个数c，只需要将树以c为关键字拆分成x树与y树。那么很明显，x树中的所有点均<=c，y树中的数均>=c,这时候只需要将c生成一个新点，将其合并到x树中，最后再将x与y合并即可。

代码如下

void insert(int c)
{
    split(root,c-1,x,y);
    root=merge(merge(x,get_node(c)),y);
}

2、删除一个数c，只需要将树以c为关键字拆分成x树与z树。再将x树以c-1拆分成x树与y树，那么很明显，y树中的所有点均==c，如果只需要删除其中一个，将y的左右子树合并后与x，z树分别合并即可。如果要将c全部删除，将x，z树合并即可。

代码如下

void dele(int c)
{
    split(root,c,x,z);
    split(x,c-1,x,y);
    if(y)
    {
        y=merge(tr[y].l,tr[y].r);
    }
    root=merge(merge(x,y),z);
}

3、查找数x在序列中的排名，将树以c-1拆分成x树与y树，此时x树的大小即为答案。

代码如下

int getrank(int c)
{
    split(root,c-1,x,y);
    int ans=tr[x].size;
    root=merge(x,y);
    return ans;
}

4、查找排名为x的数的值，如果当前根节点加上左子树中的数字个数==c那么说明，答案就是跟节点，否则如果>c，则说明答案在左子树中，递归查找即可，最后便只可能在右子树中，此时应该注意，递归时应将左子树与根节点的个数减去，即为在右子树中的排名。

代码如下

int getnum(int c)
{
    int p=root;
    while(1)
    {
        if(tr[tr[p].l].size + 1==c) break;
        else if(tr[tr[p].l].size+1 > c) p=tr[p].l;
        else c=c-tr[tr[p].l].size-1,p=tr[p].r;
    }
    return tr[p].key;
}

5、查找数x的前驱，将树分以c-1为关键字划分成x树与y树，此时，x树中的最大值便是答案，只需递归搜x树中的右子树直到没有右子树位置，最后记得将树合并回来。

代码如下

int getlast(int c)
{
     split(root,c-1,x,y);
     int p=x;
     while(tr[p].r) p=tr[p].r; 
     int ans=tr[p].key;
     root=merge(x,y);
     return ans;
}

6、查找数x的后继，将树分以c为关键字划分成x树与y树，此时，y树中的最小值便是答案，只需递归搜y树中的左子树直到没有左子树位置，最后记得将树合并回来。

代码如下

int getnext(int key) 
{
     int x, y;
     int ans;
     split(root, key, x, y);
     int p = y;
     while (tr[p].l) p = tr[p].l;
     ans = tr[p].key;
     root = merge(x, y);
     return ans;
}

在充分理解了上述6个操作后便可以愉快地将模板题AC了，本人AC代码如下，仅供参考。

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
const int N=100010;

struct Node
{
    int l,r;
    int key,val;
    int size;
}tr[N];

int idx,root;
int x,y,z;

void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
}

int get_node(int c)
{
     tr[++idx].key=c;
     tr[idx].val=rand();
     tr[idx].size=1;
     return idx;
}

void split(int p,int key,int &x,int &y)
{
    if(!p) 
    {
        x=y=0;
        return;
    }
    else
    {
        if(tr[p].key <= key)
            x=p,split(tr[p].r,key,tr[p].r,y);
        else
            y=p,split(tr[p].l,key,x,tr[p].l);
    }
    pushup(p);
}

int merge(int a,int b)
{
    if(a==0 or b==0) return a+b;
    if(tr[a].val > tr[b].val)
    {
        tr[a].r=merge(tr[a].r,b);
        pushup(a);
        return a;
    }
    else
    {
        tr[b].l=merge(a,tr[b].l);
        pushup(b);
        return b;
    }
}

void insert(int c)
{
    split(root,c-1,x,y);
    root=merge(merge(x,get_node(c)),y);
}

void dele(int c)
{
    split(root,c,x,z);
    split(x,c-1,x,y);
    if(y)
    {
        y=merge(tr[y].l,tr[y].r);
    }
    root=merge(merge(x,y),z);
}

int getrank(int c)
{
    split(root,c-1,x,y);
    int ans=tr[x].size;
    root=merge(x,y);
    return ans;
}

int getnum(int c)
{
    int p=root;
    while(1)
    {
        if(tr[tr[p].l].size + 1==c) break;
        else if(tr[tr[p].l].size+1 > c) p=tr[p].l;
        else c=c-tr[tr[p].l].size-1,p=tr[p].r;
    }
    return tr[p].key;
}

int getlast(int c)
{
    split(root,c-1,x,y);
    int p=x;
    while(tr[p].r) p=tr[p].r; 
    int ans=tr[p].key;
    root=merge(x,y);
    return ans;
}

int getnext(int key) 
{
    int x, y;
    int ans;
    split(root, key, x, y);
    int p = y;
    while (tr[p].l) p = tr[p].l;
    ans = tr[p].key;
    root = merge(x, y);
    return ans;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int k,x;
        cin>>k>>x;
        if(k==1) insert(x);
        else if(k==2) dele(x);
        else if(k==3) cout<<getrank(x)+1<<endl;
        else if(k==4) cout<<getnum(x)<<endl;
        else if(k==5) cout<<getlast(x)<<endl;
        else if(k==6) cout<<getnext(x)<<endl;
    } 
}

在理解完模板题后，便可以找一下题小试牛刀了，但是如果掌握不熟练，依然会十分痛苦，祝好运~~

由于本人能力有限，没有进行插图，但是用了更多的文字进行描述，还请见谅，如果文中出现知识性错误，烦请斧正，感谢！