简介：

    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=0;static int sta[maxn],top;    for(int i=1;i<=n;i++)    {        x=new_node(data[i]),last=0;        while(top&&fix[sta[top]]>fix[x]) update(sta[top]),last=sta[top],sta[top--]=0;        if(top) ch[sta[top]][1]=x;        ch[x][0]=last;sta[++top]=x;    }    while(top) update(sta[top--]);    return sta[1];}

 

 

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

1： split

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

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

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

 

void split(int now,int k,int &x,int &y){    if(!now) x=y=0;    else     {        if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);        else y=now,split(ch[now][0],k,x,ch[now][0]);        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]

 

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

 

一：基本操作

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
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define maxn 500001using namespace std;int size[maxn],ch[maxn][2],fix[maxn],val[maxn];int T,cnt,n,m,x,y,z,p,a,root,com;inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
      if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}inline void update(int x){    size[x]=1+size[ch[x][0]]+size[ch[x][1]];}inline int new_node(int x){    size[++cnt]=1;    val[cnt]=x;    fix[cnt]=rand();    return cnt;}int merge(int A,int B){    if(!A||!B) return  A+B;    if(fix[A]
            
           
          
         
        

 

二：区间操作

区间提取

  分为两次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
        
         #include
         
          #include
          
           #include
           
            #define maxn 500010#define inf 0x3f3f3f3fusing namespace std;int siz[maxn],ch[maxn][2],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
            
             trashcan;inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
      if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}long int random(){    static int seed=703;    return seed=int(seed*48271LL%2147483647);}inline int max(int x,int y){
      return x>y?x:y;}inline int min(int x,int y){
      return x
             
              fix[x]) update(sta[top]),last=sta[top],sta[top--]=0; if(top) ch[sta[top]][1]=x; ch[x][0]=last;sta[++top]=x; } while(top) update(sta[top--]); return sta[1];}void split(int now,int k,int &x,int &y){ if(!now) x=y=0; else { pushdown(now); if(siz[ch[now][0]]>=k) y=now,split(ch[now][0],k,x,ch[now][0]); else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); update(now); }}int merge(int A,int B){ if(A) pushdown(A); if(B) pushdown(B); if(A*B==0) return A+B; if(fix[A]