可持久化Treap(fhq Treap，非旋转式Treap)学习(未完待续)

简介：

Treap，一种表现优异的BST

优势：

其较于AVL、红黑树实现简单，浅显易懂

较于Splay常数小，通常用于树套BST表现远远优于Splay

或许有人想说SBT，SBT我没有实现过，据说比较快

但是SBT、Splay以及旋转版Treap等BST都不可以比较方便地实现‘可持久化操作

Treap=Tree+Heap

Treap是一颗同时拥有二叉搜索树和堆性质的一颗二叉树

Treap有两个关键字，在这里定义为：

1.key，满足二叉搜索树性质，即中序遍历按照key值有序

2.fix，满足堆性质，即对于任何一颗以x为根的子树，x的fix值为该子树的最值，方便后文叙述，定义为最小值

为了满足期望，fix值是一个随机的权值，用来保证树高期望为logn

剩下的key值则是用来维护我们想要维护的一个权值，此为一个二叉搜索树的基本要素

支持操作：

基本操作：

1.Build【构造Treap】【O(n)】

2.Merge【合并】【O(logn)】

3.Split【拆分】【O(logn)】

4.Newnode【新建节点】【O(1)】

可支持操作：

1.Insert【Newnode+Merge】【O(logn)】

2.Delete【Split+Split+Merge】【O(logn)】

3.Find_kth【Split+Split】【O(logn)】

4.Query【Split+Split】【O(logn)】

5.Cover【Split+Split+Merge】【O(logn)】

and more....

先说建树，Treap属于笛卡尔树，所以建树方式同笛卡尔树

用栈维护一个fix值递增的序列即可。

代码

int build(int *data,int n)

{

    int x,last=;static int sta[maxn],top;

    for(int i=;i<=n;i++)

    {

        x=new_node(data[i]),last=;

        while(top&&fix[sta[top]]>fix[x]) update(sta[top]),last=sta[top],sta[top--]=;

        if(top) ch[sta[top]][]=x;

        ch[x][]=last;sta[++top]=x;

    }

    while(top) update(sta[top--]);

    return sta[];

}

只需要两个基础操作，就可以达到splay的所有功能

1： split

将Treap按照权值或排名分裂为两棵Treap 我只写了按权值分裂

对于我们遍历到每一个点，假如它的权值小于k，那么它的所有左子树，都要分到左边的树里，然后遍历它的右儿子。假如大于k，把它的所有右子树分到右边的树里，遍历左儿子。

因为它的最多操作次数就是一直分到底，效率就是O(logn)。

void split(int now,int k,int &x,int &y)

{

    if(!now) x=y=;

    else

    {

        if(val[now]<=k) x=now,split(ch[now][],k,ch[now][],y);

        else y=now,split(ch[now][],k,x,ch[now][]);

        update(now);

    }

}

2： merge

这个就是把两个Treap合成一个，保证第一个的权值小于第二个。

因为第一个Treap的权值都比较小，我们比较一下它的fix(附加权值)，假如第一个的fix小，我们就可以直接保留它的所有左子树，接着把第一个Treap变成它的右儿子。反之，我们可以保留第二棵的所有右子树，指针指向左儿子。

你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树，也可以理解为在第二个树的左子树上插入第一棵树。因为第一棵树都满足小于第二个树，所以就变成了比较fix来确定树的形态。

也就是说，我们其实是遍历了第一个trep的根->最大节点，第二个Treap的根->最小节点，也就是O(logn)

int merge(int A,int B)

{

    if(!A||!B) return  A+B;

    if(fix[A]<fix[B]){ch[A][]=merge(ch[A][],B); update(A); return A;}

    else {ch[B][]=merge(A,ch[B][]); update(B); return B;}

}

下面我们就可以通过这两个基本的东西实现各种各样的操作了。

一：基本操作

insertinsert

插入一个权值为v的点，把树按照v的权值split成两个，再按照顺序merge回去。

deldel

删除权值为v的点，把树按照v分成两个a,b,再把a按照v-1分成c,d。把c的两个子儿子merge起来，再merge(merge(c,d),b)

(因为把c的两个儿子merge起来之后，如果权值为v的节点有一个，就已经把他删除了,因为merge后c=0;若有多个就删除了一个)

precursorprecursor

找前驱的话把root按v-1 split成x,y，在x里面找最大值

successorsuccessor

找后继的话把root按v split成x,y，在y里找最小值

rankrank

把root按v-1 split成x,y，排名是x的siz

代码:https://www.luogu.org/problem/show?pid=3369 普通平衡树

#include<iostream>

#include<cstdio>

#include<cstring>

#include<ctime>

#include<cstdlib>

#define maxn 500001

using namespace std;

int size[maxn],ch[maxn][],fix[maxn],val[maxn];

int T,cnt,n,m,x,y,z,p,a,root,com;

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

inline void update(int x)

{

    size[x]=+size[ch[x][]]+size[ch[x][]];

}

inline int new_node(int x)

{

    size[++cnt]=;

    val[cnt]=x;

    fix[cnt]=rand();

    return cnt;

}

int merge(int A,int B)

{

    if(!A||!B) return  A+B;

    if(fix[A]<fix[B]){ch[A][]=merge(ch[A][],B); update(A); return A;}

    else {ch[B][]=merge(A,ch[B][]); update(B); return B;}

}

void split(int now,int k,int &x,int &y)

{

    if(!now) x=y=;

    else

    {

        if(val[now]<=k) x=now,split(ch[now][],k,ch[now][],y);

        else y=now,split(ch[now][],k,x,ch[now][]);

        update(now);

    }

}

int kth(int now,int k)

{

    while()

    {

        if(k<=size[ch[now][]]) now=ch[now][];

        else if(k==size[ch[now][]]+) return now;

        else k-=size[ch[now][]]+,now=ch[now][];

    }

}

int main()

{

    srand((unsigned)time(NULL));

    T=read();

    while(T--)

    {

        p=read();a=read();

        if(p==)

        {

            split(root,a,x,y);

            root=merge(merge(x,new_node(a)),y);

        }

        else if(p==)

        {

            split(root,a,x,z);

            split(x,a-,x,y);

            y=merge(ch[y][],ch[y][]);

            root=merge(merge(x,y),z);

        }

        else if(p==)

        {

            split(root,a-,x,y);

            printf("%d\n",size[x]+);

            root=merge(x,y);

        }

        else if(p==) printf("%d\n",val[kth(root,a)]);

        else if(p==)

        {

            split(root,a-,x,y);

            printf("%d\n",val[kth(x,size[x])]);

            root=merge(x,y);

        }

        else

        {

            split(root,a,x,y);

            printf("%d\n",val[kth(y,)]);

            root=merge(x,y);

        }

    }

    return ;

}

二：区间操作

区间提取

分为两次split操作第一次split(root,pos-1,x1,x2);第二次split(x2,len,y1,y2) y1就是提取出的区间注意split是按照编号split而不是权值

因此就可以进行一系列的区间操作，如区间改值，区间删除，区间插入等

bzoj1500 维修数列 http://www.lydsy.com/JudgeOnline/problem.php?id=1500

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 500010

#define inf 0x3f3f3f3f

using namespace std;

int siz[maxn],ch[maxn][],fix[maxn],val[maxn],a[maxn],f[maxn];

int tmx[maxn],lmx[maxn],rmx[maxn],sum[maxn],rev[maxn],cov[maxn];

int T,cnt,n,m,b,root,com;

queue<int>trashcan;

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

long int random()

{

    static int seed=;

    return seed=int(seed*48271LL%);

}

inline int max(int x,int y){return x>y?x:y;}

inline int min(int x,int y){return x<y?x:y;}

void swap(int &a,int &b){a^=b;b^=a;a^=b;}

int new_node(int v)

{

    int x;

    if(!trashcan.empty()) x=trashcan.front(),trashcan.pop();

    else x=++cnt;

    ch[x][]=ch[x][]=rev[x]=;

    cov[x]=inf;fix[x]=random();siz[x]=;

    val[x]=sum[x]=tmx[x]=v;

    lmx[x]=rmx[x]=max(v,);

    return x;

}

void update(int x)

{

    if(ch[x][]&&ch[x][])

    {

        siz[x]=+siz[ch[x][]]+siz[ch[x][]];

        sum[x]=sum[ch[x][]]+sum[ch[x][]]+val[x];

        tmx[x]=max(tmx[ch[x][]],tmx[ch[x][]]);

        tmx[x]=max(tmx[x],rmx[ch[x][]]+val[x]+lmx[ch[x][]]);

        lmx[x]=max(lmx[ch[x][]],sum[ch[x][]]+val[x]+lmx[ch[x][]]);

        rmx[x]=max(rmx[ch[x][]],sum[ch[x][]]+val[x]+rmx[ch[x][]]);

    }

    else if(ch[x][])

    {

        siz[x]=siz[ch[x][]]+;

        sum[x]=sum[ch[x][]]+val[x];

        tmx[x]=max(tmx[ch[x][]],rmx[ch[x][]]+val[x]);

        lmx[x]=max(lmx[ch[x][]],sum[ch[x][]]+val[x]);

        lmx[x]=max(,lmx[x]);

        rmx[x]=max(,val[x]+rmx[ch[x][]]);

    }

    else if(ch[x][])

    {

        siz[x]=siz[ch[x][]]+;

        sum[x]=sum[ch[x][]]+val[x];

        tmx[x]=max(tmx[ch[x][]],lmx[ch[x][]]+val[x]);

        rmx[x]=max(rmx[ch[x][]],sum[ch[x][]]+val[x]);

        rmx[x]=max(,rmx[x]);

        lmx[x]=max(,lmx[ch[x][]]+val[x]);

    }

    else

    {

       siz[x]=,sum[x]=tmx[x]=val[x];

       lmx[x]=rmx[x]=max(val[x],);

    }

}

void reverse(int x)

{

    swap(ch[x][],ch[x][]);

    swap(lmx[x],rmx[x]);

    rev[x]^=;

}

void cover(int x,int v)

{

    val[x]=v;sum[x]=siz[x]*v;

    lmx[x]=rmx[x]=max(sum[x],);

    tmx[x]=max(sum[x],val[x]);

    cov[x]=v;

}

void pushdown(int x)

{

    if(rev[x])

    {

        if(ch[x][]) reverse(ch[x][]);

        if(ch[x][]) reverse(ch[x][]);

    }

    if(cov[x]!=inf)

    {

        if(ch[x][]) cover(ch[x][],cov[x]);

        if(ch[x][]) cover(ch[x][],cov[x]);

    }

    rev[x]=;cov[x]=inf;

}

int build(int *data,int n)

{

    int x,last=;static int sta[maxn],top;

    for(int i=;i<=n;i++)

    {

        x=new_node(data[i]),last=;

        while(top&&fix[sta[top]]>fix[x]) update(sta[top]),last=sta[top],sta[top--]=;

        if(top) ch[sta[top]][]=x;

        ch[x][]=last;sta[++top]=x;

    }

    while(top) update(sta[top--]);

    return sta[];

}

void split(int now,int k,int &x,int &y)

{

    if(!now) x=y=;

    else

    {

        pushdown(now);

        if(siz[ch[now][]]>=k) y=now,split(ch[now][],k,x,ch[now][]);

        else x=now,split(ch[now][],k-siz[ch[now][]]-,ch[now][],y);

        update(now);

    }

}

int merge(int A,int B)

{

    if(A) pushdown(A); if(B) pushdown(B);

    if(A*B==) return A+B;

    if(fix[A]<fix[B]){ch[A][]=merge(ch[A][],B);update(A);return A;}

    else{ch[B][]=merge(A,ch[B][]);update(B);return B;}

}

void trash(int x)

{

    if(!x) return;

    trashcan.push(x);

    trash(ch[x][]); trash(ch[x][]);

}

void insert()

{

    int pos=read(),len=read(),x,y; static int datas[maxn];

    for(int i=;i<=len;i++) datas[i]=read();

    int rt=build(datas,len);

    split(root,pos,x,y);

    root=merge(merge(x,rt),y);

}

void del()

{

    int pos=read(),len=read(),x1,x2,y1,y2;

    split(root,pos-,x1,x2);

    split(x2,len,y1,y2);

    root=merge(x1,y2); trash(y1);

}

void covers()

{

    int pos=read(),len=read(),v=read(),x1,x2,y1,y2;

    split(root,pos-,x1,x2);

    split(x2,len,y1,y2);

    cover(y1,v);

    root=merge(x1,merge(y1,y2));

}

void reverses()

{

    int pos=read(),len=read(),x1,x2,y1,y2;

    split(root,pos-,x1,x2);

    split(x2,len,y1,y2); reverse(y1);

    root=merge(x1,merge(y1,y2));

}

void sums()

{

    int pos=read(),len=read(),x1,x2,y1,y2;

    split(root,pos-,x1,x2);

    split(x2,len,y1,y2);

    printf("%d\n",sum[y1]);

    root=merge(x1,merge(y1,y2));

}

int main()

{

    n=read();m=read();

    for(int i=;i<=n;i++)

      a[i]=read();

    root=build(a,n);

    static char s[];

    while(m--)

    {

        scanf("%s",s);

        if(s[]=='I') insert();

        else if(s[]=='D') del();

        else if(s[]=='M'&&s[]=='K') covers();

        else if(s[]=='R') reverses();

        else if(s[]=='G') sums();

        else printf("%d\n",tmx[root]);

    }

    return ;

}

巴特西