Treap模板

前几日闲的没事写个平衡树练手，挑个最简单的当然就是Treap，十几分钟大概就可以写出来。

Treap是一棵二叉搜索树（自然满足二叉搜索树的性质），同时节点有一个rand出来的key值，根据这个key值treap同时还是一个堆。

这个是百度百科的链接，具体原理可以参考

我们都知道平衡树的调整都需“旋”，但是“旋”这个东西本身比较抽象代码也不直观，这里的实现利用“分割”和“合并”代替了一般平衡树的“旋转”操作

有一个不错的视频可以参考

博客中不再多余赘述，直接看代码就行了

namespace treap{    int key[maxn],val[maxn],ls[maxn]={0},rs[maxn]={0},_size[maxn]={0};    int tot=0;    inline void push_up(int x){        _size[x]=_size[ls[x]]+_size[rs[x]]+1;    }    void Split(int root,int &x,int &y,int v){        if(root==0){            x=y=0;            return;        }        if(val[root]<=v) x=root,Split(rs[x],rs[x],y,v);        else y=root,Split(ls[y],x,ls[y],v);        push_up(root);    }    void Merge(int& root,int x,int y){        if(x==0||y==0){            root=x+y;            return;        }        if(key[x]
    
     =k)root=ls[root];            else k=k-_size[ls[root]]-1,root=rs[root];        }        return val[root];    }    int get_Rank(int &root,int v){        int x=0,y=0;        Split(root,x,y,v-1);        int ret=_size[x]+1;        Merge(root,x,y);        return ret;    }    int Lower(int &root,int v){        int x=0,y=0;        Split(root,x,y,v-1);        int ret=Kth(x,_size[x]);        Merge(root,x,y);        return ret;    }    int Upper(int &root,int v){        int x=0,y=0;        Split(root,x,y,v);        int ret=Kth(y,1);        Merge(root,x,y);        return ret;    }}