Treap

Subs_zh · 2021-10-14 22:17:38 · 个人记录

Treap

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 1000050
using namespace std;
int n;
struct Treap{//Treap:BST+小根堆（随机权值保证BST不是一条链继而保证复杂度) 
    //0:left;1:right
    int root,tot,siz[maxn],w[maxn],pos[maxn];
    int s[maxn][2];
    void push_up(int i){siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;}
    void rotate(int &i,int p)
    {
        int t=s[i][p];
        s[i][p]=s[t][!p];
        s[t][!p]=i;
        push_up(i); push_up(t);
        i=t;
    }
    void ins(int x,int &i)
    {
        if(!i){i=++tot;siz[i]=1;w[i]=x;pos[i]=rand();return;}
        siz[i]++;
        int p=(x>w[i]?1:0);
        ins(x,s[i][p]);
        if(pos[s[i][p]]<pos[i]) rotate(i,p);//将i和儿子p交换 
    }    
    void del(int x,int &i)
    {
        if(w[i]==x)
        {
            if(!s[i][0]||!s[i][1]){i=s[i][0]+s[i][1];return;}
            int p=pos[s[i][0]]>pos[s[i][1]]?1:0;
            rotate(i,p); del(x,s[i][p^1]);
        }
        else if(w[i]>x)del(x,s[i][0]);
        else del(x,s[i][1]);
        push_up(i);
    }
    int queryrank(int x,int i)//寻找x的排名
    {
        if(!i)return 1;
        if(w[i]>=x)return queryrank(x,s[i][0]);
        else return queryrank(x,s[i][1])+siz[s[i][0]]+1;
    }
    int queryk(int x,int i)//寻找第x大 
    {
        if(siz[s[i][0]]==x-1)return w[i];
        if(siz[s[i][0]]>=x)return queryk(x,s[i][0]);
        else return queryk(x-siz[s[i][0]]-1,s[i][1]);
    }
    int querypre(int x,int i)//找前驱
    {
        if(!i)return -inf;
        if(w[i]<x)return max(w[i],querypre(x,s[i][1]));
        else return querypre(x,s[i][0]);
    }
    int querynxt(int x,int i)
    {
        if(!i)return inf;
        if(w[i]>x)return min(w[i],querynxt(x,s[i][0]));
        else return querynxt(x,s[i][1]);
    }
}tr;

int main()
{
    //srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int opt,x; scanf("%d%d",&opt,&x);
        if(opt==1)tr.ins(x,tr.root);
        if(opt==2)tr.del(x,tr.root);
        if(opt==3)cout<<tr.queryrank(x,tr.root)<<endl;
        if(opt==4)cout<<tr.queryk(x,tr.root)<<endl;
        if(opt==5)cout<<tr.querypre(x,tr.root)<<endl;
        if(opt==6)cout<<tr.querynxt(x,tr.root)<<endl;
    }
}

无旋Treap

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,rt;
struct fhqTreap{//将Treap的主属性从BST转为小根堆, pos[]:按小根堆排列; w[]:按BST排列
    int w[maxn],siz[maxn],pos[maxn],tot;
    int s[maxn][2];
    int lazy[maxn];//lazy标记：区间是否翻转 
    void push_up(int i){siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;}
    void push_down(int i)//区间翻转下传标记 
    {
        swap(s[i][0],s[i][1]);
        if(s[i][0])lazy[s[i][0]]^=1;
        if(s[i][1])lazy[s[i][1]]^=1;
        lazy[i]=0;
    }
    int newcode(int x)
    {
        w[++tot]=x;siz[tot]=1;pos[tot]=rand();
        return tot;
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x+y;
        if(pos[x]<pos[y])//以x为根
        {
            if(lazy[x]) push_down(x);
            s[x][1]=merge(s[x][1],y); push_up(x);
            return x;
        }
        else
        {
            if(lazy[y]) push_down(y);
            s[y][0]=merge(x,s[y][0]); push_up(y);
            return y;
        }
    }
    void split(int i,int k,int &x,int &y)
    {
        if(!i){ x=y=0; return; }
        if(lazy[i])push_down(i);
        if(k<=siz[s[i][0]])
            y=i,split(s[i][0],k,x,s[i][0]);
        else 
            x=i,split(s[i][1],k-siz[s[i][0]]-1,s[i][1],y);
        push_up(i);
    }
    void print(int i)
    {
        if(!i)return;
        if(lazy[i])push_down(i);
        print(s[i][0]);
        printf("%d ",w[i]);
        print(s[i][1]);
    }
    int query(int now,int k)//查询排名为k的数
    {
        if(k==siz[s[now][0]]+1)return w[now];
        if(lazy[now])push_down(now);
        if(k<=siz[s[now][0]])
            return query(s[now][0],k);
        else return query(s[now][1],k-siz[s[now][0]]-1);
    }
}tr;

void ins(int a)//插入一个元素
{
    int x,y;
    tr.split(rt,a,x,y);
    rt=tr.merge(tr.merge(x,tr.newcode(a)),y);
}
void del(int x)//删除一个元素
{
    int a,b,c;
    tr.split(rt,x,b,c);
    tr.split(b,x-1,a,b);
    b=tr.merge(tr.s[b][0],tr.s[b][1]);
    rt=tr.merge(tr.merge(a,b),c);

}
int queryrank(int k)//查询数k的排名
{
    int x,y,z,ret;
    tr.split(rt,k-1,x,y);
    ret=tr.siz[x]+1;
    rt=tr.merge(x,y);
    return ret;
}
int querypre(int k)//查询数k的前驱
{
    int x,y,ret;
    tr.split(rt,k-1,x,y);
    ret=tr.query(x,tr.siz[x]);
    rt=tr.merge(x,y);
    return ret;
}
int querynxt(int k)//查询数k的后继
{
    int x,y,ret;
    tr.split(rt,k,x,y);
    ret=tr.query(y,1);//查询y中第一个数
    rt=tr.merge(x,y);
    return ret;
}
void turn(int l,int r)//翻转区间[l,r]
{
    int a,b,c;
    tr.split(rt,r,b,c);
    tr.split(b,l-1,a,b);
    tr.lazy[b]^=1;
    rt=tr.merge(a,tr.merge(b,c));
}
int main()
{
    n=read(); 
    for(int i=1;i<=n;i++) 
    {
        int opt=read(); int x=read();
        if(opt==1)ins(x);
        if(opt==2)del(x);
        if(opt==3)printf("%lld\n",queryrank(x));
        if(opt==4)printf("%lld\n",tr.query(rt,x));
        if(opt==5)printf("%lld\n",querypre(x));
        if(opt==6)printf("%lld\n",querynxt(x));
        if(opt==7){ int l=x,r=read();turn(l,r);}
        if(opt==8){tr.print(rt);cout<<endl;}
    }
}

Treap和笛卡尔树

例题：文本编辑器

利用笛卡尔树建树，O（n）建树减少复杂度。

 int build(int *a,int k)
    {
        int top=0;
        for(int i=1;i<=k;i++)
        {
            newcode(a[i]);int l=0;
            while(top&&pos[st[top]]>pos[tot])push_up(st[top]),l=st[top--];
            if(top)s[st[top]][1]=tot;
            s[tot][0]=l;
            st[++top]=tot;
        }
        while(top)
        {
            push_up(st[top--]);
        }
        return st[1];
    }

按排名split与按权值split

排名：

    void split(int i,int k,int &x,int &y)
    {
        if(!i){ x=y=0; return; }
        if(lazy[i])push_down(i);
        if(k<=siz[s[i][0]])//第i个节点在y中
            y=i,split(s[i][0],k,x,s[i][0]);
        else 
            x=i,split(s[i][1],k-siz[s[i][0]]-1,s[i][1],y);
        push_up(i);
    }

权值：

    void split(int i,nod k,int &x,int &y)
    {
        if(!i){x=y=0;return;}
        if(w[i]>k)//第i个节点在y中
            y=i,split(s[i][0],k,x,s[i][0]);
        else 
            x=i,split(s[i][1],k,s[i][1],y);
        push_up(i);
    }

无旋Treap删除一个元素

    int x,y,z; 
    tr.split(rt,a,x,y);
    tr.split(x,a-1,x,z);
    z=tr.merge(tr.s[z][0],tr.s[z][1]);
    rt=tr.merge(tr.merge(x,z),y);