范浩强treap——可持久化

当平衡树需要可持久化的时候，意味着我们需要访问以前的某个时间点的平衡树，就要保持以前的树形态不变，新建一个时间戳，构建一棵新的树。

如果用以前的旋转treap可能就不方便做到（又要打时间戳，又要新建节点，又要旋转），而且涉及到旋转，空间可能会承受不住，我们需要用到一种新的平衡树——fhq treap

这是一种非常好写的treap 核心操作有两个，一个是split一个是merge。

split(node,k,x,y) 意思是把以node为跟的子树分成两部分，一部分小于等于k（根为x），一部分大于k（根为y）。在可持久化的时候要保证以前的树的形态不变，就要每一次copy一个节点过来。

而我们每一次递归只会访问一个节点的左右子树中的一个节点，又因为treap的均摊深度为log，所以总体的空间为nlogn，是非常高效的。

说完split接下来是merge

merge函数，是有返回值的，merge(x,y) 是把以x为根的子树和以y为根的子树合并起来，返回这棵新的树的根，递归的实现，非常好懂。

接下来的所有操作都是基于以上两个核心的操作，非常好理解，比旋转的treap好理解而且更好写，注意可持久化即可。

——by VANE

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;

 struct node

 {

     int ch[];

     int fix,key,sz;

 }t[N*];

 int root[N],cnt=;

 int copynode(int x)

 {

     cnt++;

     t[cnt]=t[x];

     return cnt;

 }

 void update(int cur)

 {

     if(cur)

     t[cur].sz=t[t[cur].ch[]].sz+t[t[cur].ch[]].sz+;

 }

 int newnode(int val)

 {

     cnt++;

     t[cnt].ch[]=t[cnt].ch[]=;

     t[cnt].key=val;

     t[cnt].sz=;

     t[cnt].fix=rand();

     return cnt;

 }

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

 {

     if(!now) x=y=;

     else

     {

         if(t[now].key<=k)

         {

             x=copynode(now);

             split(t[x].ch[],k,t[x].ch[],y);

         }

         else

         {

             y=copynode(now);

             split(t[y].ch[],k,x,t[y].ch[]);

         }

         update(x);

         update(y);

     }

 }

 int merge(int x,int y)

 {

     if(!x||!y) return x+y;

     if(t[x].fix<t[y].fix)

     {

         int r=copynode(x);

         t[r].ch[]=merge(t[r].ch[],y);

         update(r);

         return r;

     }

     else

     {

         int r=copynode(y);

         t[r].ch[]=merge(x,t[r].ch[]);

         update(r);

         return r;

     }

 }

 void insert(int bb,int val)

 {

     int x,y,z;

     x=y=z=;

     split(root[bb],val,x,y);

     z=newnode(val);

     root[bb]=merge(merge(x,z),y);

 }

 void Delete(int bb,int val)

 {

     int x,y,z;

     split(root[bb],val,x,z);

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

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

     root[bb]=merge(merge(x,y),z);

 }

 int getpos(int now,int k)

 {

     while()

     {

         if(k<=t[t[now].ch[]].sz) now=t[now].ch[];

         else if(k==t[t[now].ch[]].sz+) return now;

         else k-=t[t[now].ch[]].sz+,now=t[now].ch[];

     }

 }

 int getkth(int bb,int val)

 {

     int x,y;

     int ret;

     split(root[bb],val-,x,y);

     ret=t[x].sz+;

     return ret;

 }

 int getval(int now,int k)

 {

     int x;

     x=getpos(now,k);

     return t[x].key;

 }

 int getpre(int bb,int val)

 {

     int x,y;

     int k,ret;

     split(root[bb],val-,x,y);

     if(x) k=t[x].sz;

     else return -;

     ret=getval(x,k);

     return ret;

 }

 int getnext(int bb,int val)

 {

     int x,y;

     split(root[bb],val,x,y);

     if(!y) return ;

     int ret=getval(y,);

     return ret;

 }

 int main()

 {

     int n,bb,cmd,val;

     scanf("%d",&n);

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

     {

         scanf("%d%d%d",&bb,&cmd,&val);

         root[i]=root[bb];

         switch(cmd)

         {

             case :insert(i,val);break;

             case :Delete(i,val);break;

             case :printf("%d\n",getkth(i,val));break;

             case :printf("%d\n",getval(root[i],val));break;

             case :printf("%d\n",getpre(i,val));break;

             case :printf("%d\n",getnext(i,val));break;

         }

     }

 }

巴特西

范浩强treap——可持久化

最新文章

热门文章