fhq_treap学习笔记【平衡树】

点击量：212

    fhq_treap是一个比较好写，扩展性强，并且可以完成splay所有操作的常数不大的数据结构。

    fhq_treap不用旋转，它基于重构，也就是平衡树的合并和分裂。它可以通过一系列操作做到像splay一样分出一棵节点权值全部小于等于$ x$的和一棵节点权值全部比$ x$大的两棵树。它的思路是类似可持久化线段树，每次只基于一条链就可以重构出一棵新的并保持平衡的treap。

    分裂的过程就是沿着一条链，把小于$ x$的元素（及其子树）加到左新树中，或把大于$ x$的元素（及其子树）加到右新树中。并沿着一条更接近$ x$的链递归处理。

    而合并的过程就是把两棵没有交集的一小一大的树，按照小根堆的原则，如果当前左边的子树权值较小，就把右边子树放在这个子树右面，递归下一层继续执行；如果右边子树权值较小，就把左边子树接在右边子树的左边，再递归执行。

    只要这样递归下去，就能完成分裂和合并的操作，一次分裂和合并，就是在重构这一棵treap了。

    对于普通平衡树一题的其他操作，可以通过分裂等操作方便地完成。实在不行也可以模拟splay的操作，因为这棵树依靠随机数保持平衡，总是趋近$ \log n$的树高，因此每次模拟查询也是$ \log n$的。

Code：

#include<cstdio>
#include<cstring>
#include<cstdlib>
struct node
{
    int key,rdm;
    int sz;
    node *ls,*rs;
    node(int key)
    {
        sz=1;
        this->key=key;
        rdm=rand();
        ls=NULL;
        rs=NULL;
    }
    int getsz()
    {
        if(!this)
            return 0;
        return sz;
    }
    void maintain()//维护操作
    {
        sz=ls->getsz()+1+rs->getsz();
    }
}*root;

node *Merge(node *a,node *b)
{
    if(!a||!b)
        return a?a:b;
    if(a->rdm<b->rdm)//小根堆
    {
        a->rs=Merge(a->rs,b);//把树b接到自己右儿子
        a->maintain();
        return a;
    }
    else
    {
        b->ls=Merge(a,b->ls);//把树a接到自己左儿子
        b->maintain();
        return b;
    }
}

void split(node *rt,int x,node *&a,node *&b)
{
    if(!rt)
    {
        a=NULL;
        b=NULL;
        return;
    }
    if(rt->key<=x)
    {
        split(rt->rs,x,rt->rs,b);
        a=rt;//把自己赋值给上面带下来的a
    }
    else
    {
        split(rt->ls,x,a,rt->ls);
        b=rt;
    }
    rt->maintain();
    return;
}

void Insert(node *&rt,int x)
{
    node *a,*b;
    split(rt,x,a,b);
    rt=Merge(Merge(a,new node(x)),b);
}

void Delete(node *&rt,int x)
{
    node *a,*b,*c;
    split(rt,x,a,b);
    split(a,x-1,a,c);
    if(c)
        c=Merge(c->ls,c->rs);
    rt=Merge(Merge(a,c),b);
}

int Rank(node *rt,int x)
{
    node *a,*b;
    split(rt,x-1,a,b);
    int ans=a->getsz()+1;
    rt=Merge(a,b);//做完要合并啊qwq
    return ans;
}

int kth(node *rt,int x)
{
    if(rt->ls->getsz()+1==x)
        return rt->key;
    if(rt->ls->getsz()>=x)//模拟splay
        return kth(rt->ls,x);
    return kth(rt->rs,x-rt->ls->getsz()-1);
}

int pre(node *rt,int x)
{
    node *a,*b;
    split(rt,x-1,a,b);//分裂就方便一些
    int ans=kth(a,a->getsz());
    rt=Merge(a,b);
    return ans;
}

int suc(node *rt,int x)
{
    node *a,*b;
    split(rt,x,a,b);
    int ans=kth(b,1);
    rt=Merge(a,b);
    return ans;
}

int main()
{
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1)
            Insert(root,x);
        else if(op==2)
            Delete(root,x);
        else if(op==3)
            printf("%d\n",Rank(root,x));
        else if(op==4)
            printf("%d\n",kth(root,x));
        else if(op==5)
            printf("%d\n",pre(root,x));
        else
            printf("%d\n",suc(root,x));
    }
    return 0;
}