模板——Treap

太过爱你忘了你带给我的痛 2021-11-26 13:14 219阅读 0赞

不得不说平衡树博大精深，除了Treap，还有splay，非旋Treap和可持久化数据结构，今天先讲讲Treap，也很感谢这位大佬的博客给予我帮助：http://www.360doc.com/content/19/0120/11/5315\_810146183.shtml

Treap的核心就是Tree+Heap，即在二叉搜索树的基础上根据随机数生成的优先级使树保持堆的性质，从而实现使Treap的深度不会太大的效果

核心操作就是旋转：人工YY一下……发现旋转有左旋（Zag）和右旋（Zig）两种操作，旋转时连三条边，即原顶点和新儿子的边，新定点作为原顶点父亲的边，以及上一级父亲连向新顶点的边。顶点和儿子连接的边先处理，用&p始终维护顶点坐标，因为传入的是son\[father\[p\]\],所以p变化时它父亲的儿子会自动变化，所以通过取址可以自动连边 （rotate下一层的p是上一层的son，p变上一层son就变） （详见代码）

除了insert和delete操作中需要rotate（delete要把删除点转到叶子结点再删去，insert在插入后要旋转以维护heap的性质，不要忘记操作之后要push\_up），其它的代码都和二叉搜索树一样

[模板题：][Link 1]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod=998244353;
    const int N=1000002;
    const int inf=(int)2e9;
    int R=0;
    
    int ran()
    {
        static ll seed=19260817;
        seed=seed*3%mod;
        return (int)seed;
    }
    
    struct node
    {
        int rnd,val,sz,ch[2],num;
        node(){}
        node(int val,int sz,int num):val(val),sz(sz),num(num){
            rnd=ran();//大根堆 
            ch[0]=ch[1]=0;//和上方函数不能同时使用，若去掉该句会MLE 
        }
    }a[1000002];
    int sum_node=0;//同一节点内的相同数字的个数 
    
    void push_up(int x)
    {
        a[x].sz=a[x].num+a[a[x].ch[0]].sz+a[a[x].ch[1]].sz;
    }
    
    void rotate(int &p,int d)//0:Zag 1:Zig
    {
        int k=a[p].ch[d^1];
        a[p].ch[d^1]=a[k].ch[d];
        a[k].ch[d]=p;
        push_up(p);
        push_up(k);
        p=k;//传入的是son[father],father连边自动变 
    }
    
    void insert(int &p,int x)
    {
        if(!p)
        {
            p=++sum_node;
            node tmp(x,1,1);
            a[p]=tmp;
            return;
        }
        if(a[p].val==x)
        {
            a[p].num++;
            a[p].sz++;
            return;
        }
        int d=(int)(x>a[p].val);
        insert(a[p].ch[d],x);
        if(a[p].rnd<a[a[p].ch[d]].rnd) rotate(p,d^1);//大根堆 
        //本一级rotate传入的p就是上一级insert传入的son 
        push_up(p);
        return;
    }
    
    void del(int &p,int x)
    {
        if(!p) return;
        if(a[p].val>x) del(a[p].ch[0],x);
        else if(a[p].val<x) del(a[p].ch[1],x);
        else
        {
            if(!a[p].ch[0]&&!a[p].ch[1])
            {
                a[p].num--; a[p].sz--;
                if(a[p].num==0) p=0;
            }
            else if(a[p].ch[0]&&!a[p].ch[1])
            {
                rotate(p,1);
                del(a[p].ch[1],x);
            }
            else if(!a[p].ch[0]&&a[p].ch[1])
            {
                rotate(p,0);
                del(a[p].ch[0],x);//之前写反了 
            }
            else
            {
                int d=(int)(a[a[p].ch[0]].rnd>a[a[p].ch[1]].rnd);
                rotate(p,d);
                del(a[p].ch[d],x);
            }
        }
        push_up(p);
    }
    
    int rnk(int p,int x)//以p为根的x的rank
    {
        if(p==0) return 0;//important
        if(x>a[p].val)
        {
            return a[a[p].ch[0]].sz+a[p].num+rnk(a[p].ch[1],x);
        }
        else if(x<a[p].val)
        {
            return rnk(a[p].ch[0],x);
        }
        else
        {
            return a[a[p].ch[0]].sz+1;
        }
    }
    
    int find(int p,int x)//已知rank查数 
    {
        if(!p) return 0;
        if(a[a[p].ch[0]].sz+a[p].num<x)//important(num)
        {
            return find(a[p].ch[1],x-a[a[p].ch[0]].sz-a[p].num);
        }
        else if(a[a[p].ch[0]].sz>=x)//>=!!!
        {
            return find(a[p].ch[0],x);
        }
        else
        {
            return a[p].val;
        }
    }
    
    int pre(int p,int x)
    {
        if(!p) return -inf;
        if(a[p].val>=x)
        {
            return pre(a[p].ch[0],x);
        }
        else return max(a[p].val,pre(a[p].ch[1],x));
    }
    
    int suc(int p,int x)
    {
        if(!p) return inf;
        if(a[p].val<=x)
        {
            return suc(a[p].ch[1],x);
        }
        else return min(a[p].val,suc(a[p].ch[0],x));
    }
    
    int n;
    int main()
    {
        //freopen("r","Treap.in",stdin);
        //freopen("w","Treap.out",stdout);
        //node x(0,0,0); a[0]=x;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int opt,x;
            scanf("%d%d",&opt,&x);
            if(opt==1) insert(R,x);//R每次会随着p改变 
            else if(opt==2) del(R,x);
            else if(opt==3) printf("%d\n",rnk(R,x));
            else if(opt==4) printf("%d\n",find(R,x));
            else if(opt==5) printf("%d\n",pre(R,x));
            else  printf("%d\n",suc(R,x));
        }
        //fclose(stdin); fclose(stdout);
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11182519.html

[Link 1]: https://www.luogu.org/problemnew/show/P3369
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211126/1212696c5a8a4d81ae084ee212c385c7.png