@KirinBill 2017-09-18T04:27:43.000000Z 字数 9859 阅读 2814

非旋转式Treap学习笔记

学习笔记 数据结构

目录

非旋转式Treap学习笔记

基础知识

定义

实现

Build

Split

Merge

NewNode

Insert

Delete

GetRank

KthVal

Predecessor

Successor

Reverse

练习

[洛谷 P3369] 普通平衡树

[洛谷 P3391] 文艺平衡树

[2017.9.9 NOIP模拟赛] 完整的海报

应用

作为普通的平衡树

可持久化

基础知识

定义

这种Treap貌似是范浩强神犇发明的（因为又叫FHQ Treap）；
顾名思义，这种Treap是没有旋转操作的；
它的核心是两个函数——分裂split()和合并merge()，~~咋跟Splay似的~~，但其作用要强大的多，几乎所有操作都是通过这两个函数来实现的，而且也能完成所有Splay维护序列的操作。
没有旋转，节点甚至不需要记录父亲，而且不改变原树节点父子关系的性质也可以让它很方便的可持久化（见文末我学习笔记的链接）；
但是，由于插入、删除等操作涉及多次分裂与合并，相较一般的Treap慢了不少（约2倍...），不过比Splay还是稍快一点的。。。

实现

一些约定：记 $key(u)$ 为 $u$ 的随机优先级， $val(u)$ 为 $u$ 的权值， $size(u),ls(u)$ 等类似。这里的Treap是小根堆。

底层函数：

Build

建树。。。

同笛卡尔树建树方法。

Split

按值的大小或序列顺序将Treap分为两个，返回两个根（即左树的节点值小于等于某个值，或左树节点为维护的序列的前k个）。

以下仅讨论按值的大小分裂，按序列顺序的类似。
考虑递归的实现，对于给定的值 $val$ ，若当前节点 $u$ 的值 $val(u)>val$ ，则一定从 $u$ 的左子树中分裂；若当前节点 $u$ 的值 $val(u) \leq val$ 则应在右子树中分裂；

对于递归后的返回值 $ret$ ，若从左子树递归返回，说明 $ls(u)$ 可能因分裂被修改，应让 $ls(u)=ret.lrt$ 。而后因为 $u$ 是当前子树的根，作为 $ls(u)$ 的父亲，替代了 $ls(u)$ ，应让 $ret.lrt=u$ 而后返回 $ret$ 。从右子树递归返回类似。

代码：

//按值的大小分裂
dual_rt split(int u,int val){
        dual_rt ret(0,0);
        if(!u) return ret;
        if(val<d[u].val){
            ret=split(d[u].ls,val);
            d[u].ls=ret.rrt;
            ret.rrt=u;
        }
        else{
            ret=split(d[u].rs,val);
            d[u].rs=ret.lrt;
            ret.lrt=u;
        }
        upd(u);
        return ret;
}

//按序列顺序分裂
dual_rt split(int u,int k){
        dual_rt ret(0,0);
        if(!u) return ret;
        push_d(u); //区间翻转的tag
        if(k<=d[d[u].ls].sz){
            ret=split(d[u].ls,k);
            d[u].ls=ret.rrt;
            ret.rrt=u;
        }
        else{
            ret=split(d[u].rs,k-d[d[u].ls].sz-1);
            d[u].rs=ret.lrt;
            ret.lrt=u;
        }
        upd(u);
        return ret;
}

Merge

给定两个相对有序的Treap（任意左树节点的值都严格小于右树节点的值，或任意左树节点的在维护的原序列中的位置都严格小于右树节点），将其合并为一个Treap，返回合并后Treap的根。

考虑两个Treap已经相对有序了，我们只需考虑使其满足堆性质即可；
考虑递归实现，对于当前两个节点 $u,v$ ，若 $key(u)<key(v)$ ，则 $u$ 应该在合并后的该子树的根。又因为两个Treap相对有序，所以 $rs(u)=merge(rs(u),v)$ ，而后， $u$ 作为该子树的根返回， $key(u)>key(v)$ 同理；
递归边界也很显然，若 $u,v$ 中有一个节点为空，则到达边界，返回非空节点。

代码：

int merge(int u,int v){
        if(!u) return v;
        else if(!v) return u;
        if(d[u].key<d[v].key){
            d[u].rs=merge(d[u].rs,v);
            upd(u);
            return u;
        }
        else{
            d[v].ls=merge(u,d[v].ls);
            upd(v);
            return v;
        }
}

NewNode

新建一个节点，并返回该节点标号。

太简单了，就不说了...

代码：

int new_nd(int val){
        static int cnt=0;
        d[++cnt].val=val;
        d[cnt].key=rand();
        d[cnt].sz=1;
        return cnt;
}

功能函数：

Insert

在Treap中插入一个节点。

先将Treap在要插入的位置Split开，再NewNode一个节点并将三个Treap按顺序Merge起来。

代码：

void ist(int val){
        dual_rt x=split(rt,val);
        rt=merge(merge(x.lrt,new_nd(val)),x.rrt);
}

Delete

在Treap中删除一个节点。

先将Treap从要删除的位置Split成三个；
则分裂后中间Treap的根是要删除的节点（因为按值的大小分裂，值与被删节点相同的会在一个Treap）；
将中间Treap的根的左右子树合并为新的Treap替代中间的Treap（相当于把被删除的节点从中间的Treap挤出去了）；
最后按顺序合并三个Treap即可；

其实，非旋转式Treap还可以做到一般平衡树做不到的删除一段连续的值（做法类似）。

代码：

void del(int val){
        dual_rt x=split(rt,val);
        dual_rt y=split(x.lrt,val-1);
        y.rrt=merge(d[y.rrt].ls,d[y.rrt].rs);
        rt=merge(merge(y.lrt,y.rrt),x.rrt);
}

GetRank

查询一个值在Treap中的排名。

先将Treap按该值Split成两个（值小于要查排名的值的节点都在左Treap）；

然后 $ans$ 就等于左边Treap的大小加 $1$ .

代码：

int get_rk(int val){
        dual_rt x=split(rt,val-1);
        int ret=d[x.lrt].sz+1;
        rt=merge(x.lrt,x.rrt);
        return ret;
}

KthVal

查询Treap中排名为k的值。

和正常的Treap操作一样，不细讲了...

代码：

int kth_val(int u,int k){
        while(true){
            if(k<=d[d[u].ls].sz)
                u=d[u].ls;
            else if(d[d[u].ls].sz+1<k){
                k-=d[d[u].ls].sz+1;
                u=d[u].rs;
            }
            else break;
        }
        return d[u].val;
}
//函数重载了一次（上面的函数还有别的用途）
int kth_val(int k){return kth_val(rt,k);}

Predecessor

查询一个值在Treap中的前驱。

也很简单，将Treap按该值Split为两个（值小于要查询前驱的值的节点都在左Treap）；
那么 $ans$ 就是左Treap排名最后的节点的值；
这样常数有些大，但是会方便些。

注意：有的题需要特判不存在前趋的情况！

代码：

//用到了上面kth_val的第一个函数
int pred(int val){
        dual_rt x=split(rt,val-1);
        int ret=kth_val(x.lrt,d[x.lrt].sz);
        rt=merge(x.lrt,x.rrt);
        return ret;
}

Successor

查询一个值在Treap中的后继。

和查询前驱类似，不说了（也要注意有的题要特判不存在后继的情况）。

代码：

int succ(int val){
        dual_rt x=split(rt,val);
        int ret=kth_val(x.rrt,1);
        rt=merge(x.lrt,x.rrt);
        return ret;
}

Reverse

对于维护序列的Treap来说，将该序列中某一个区间反转一下。

和Splay类似，我们把要反转的区间Split出来，然后在这个Treap的根节点打个tag，之后合并回去就好了；
不过还得写个push_d()；

其它对序列的操作都类似，Splay能做的除了LCT，非旋转式Treap都可以！

代码：

void rvs(int l,int r){
        dual_rt x=split(rt,l-1);
        dual_rt y=split(x.rrt,r-l+1);
        d[y.lrt].rev^=true;
        rt=merge(merge(x.lrt,y.lrt),y.rrt);
}

练习

[洛谷 P3369] 普通平衡树

裸模板。。。

代码：

#include <cstdio>
#include <cstdlib>
#include <utility>
#define lrt first
#define rrt second
using std::pair;
typedef pair<int,int> dual_rt;
const int MAXN=100005;
struct node{
    int ls,rs,val,key,sz;
    friend bool operator< (const node &a,const node &b){
        return a.val<b.val;
    }
};
class FHQ_Treap{
    private:
        int rt;
        node d[MAXN];
        void upd(int u){
            d[u].sz=d[d[u].ls].sz+d[d[u].rs].sz+1;
        }
        int new_nd(int val){
            static int cnt=0;
            d[++cnt].val=val;
            d[cnt].key=rand();
            d[cnt].sz=1;
            return cnt;
        }
        dual_rt split(int u,int val){
            dual_rt ret(0,0);
            if(!u) return ret;
            if(val<d[u].val){
                ret=split(d[u].ls,val);
                d[u].ls=ret.rrt;
                ret.rrt=u;
            }
            else{
                ret=split(d[u].rs,val);
                d[u].rs=ret.lrt;
                ret.lrt=u;
            }
            upd(u);
            return ret;
        }
        int merge(int u,int v){
            if(!u) return v;
            else if(!v) return u;
            if(d[u].key<d[v].key){
                d[u].rs=merge(d[u].rs,v);
                upd(u);
                return u;
            }
            else{
                d[v].ls=merge(u,d[v].ls);
                upd(v);
                return v;
            }
        }
        int kth_val(int u,int k){
            while(true){
                if(k<=d[d[u].ls].sz)
                    u=d[u].ls;
                else if(d[d[u].ls].sz+1<k){
                    k-=d[d[u].ls].sz+1;
                    u=d[u].rs;
                }
                else break;
            }
            return d[u].val;
        }
    public:
        void ist(int val){
            dual_rt x=split(rt,val);
            rt=merge(merge(x.lrt,new_nd(val)),x.rrt);
        }
        void del(int val){
            dual_rt x=split(rt,val);
            dual_rt y=split(x.lrt,val-1);
            y.rrt=merge(d[y.rrt].ls,d[y.rrt].rs);
            rt=merge(merge(y.lrt,y.rrt),x.rrt);
        }
        int get_rk(int val){
            dual_rt x=split(rt,val-1);
            int ret=d[x.lrt].sz+1;
            rt=merge(x.lrt,x.rrt);
            return ret;
        }
        int kth_val(int k){return kth_val(rt,k);}
        int pred(int val){
            dual_rt x=split(rt,val-1);
            int ret=kth_val(x.lrt,d[x.lrt].sz);
            rt=merge(x.lrt,x.rrt);
            return ret;
        }
        int succ(int val){
            dual_rt x=split(rt,val);
            int ret=kth_val(x.rrt,1);
            rt=merge(x.lrt,x.rrt);
            return ret;
        }
}T;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1,opt,x;i<=n;++i){
        scanf("%d%d",&opt,&x);
        switch(opt){
            case 1: T.ist(x); break;
            case 2: T.del(x); break;
            case 3: printf("%d\n",T.get_rk(x));
                    break;
            case 4: printf("%d\n",T.kth_val(x));
                    break;
            case 5: printf("%d\n",T.pred(x));
                    break;
            default:printf("%d\n",T.succ(x));
        }
    }
    return 0;
}

[洛谷 P3391] 文艺平衡树

区间操作模板题。。。

代码：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#define lrt first
#define rrt second
using std::swap;
using std::pair;
using std::stack;
typedef pair<int,int> dual_rt;
const int MAXN=100005;
int tmp[MAXN];
struct node{
    int s[2],sz,val,key;
    bool rev;
};
class seq_Treap{
    private:
        int rt;
        node d[MAXN];
        void upd(int u){
            d[u].sz=d[d[u].s[0]].sz+d[d[u].s[1]].sz+1;
        }
        void push_d(int u){
            if(d[u].rev){
                swap(d[u].s[0],d[u].s[1]);
                d[d[u].s[0]].rev^=true;
                d[d[u].s[1]].rev^=true;
                d[u].rev=false;
            }
        }
        dual_rt split(int u,int k){
            dual_rt ret(0,0);
            if(!u) return ret;
            push_d(u);
            if(k<=d[d[u].s[0]].sz){
                ret=split(d[u].s[0],k);
                d[u].s[0]=ret.rrt;
                ret.rrt=u;
            }
            else{
                ret=split(d[u].s[1],k-d[d[u].s[0]].sz-1);
                d[u].s[1]=ret.lrt;
                ret.lrt=u;
            }
            upd(u);
            return ret;
        }
        int merge(int u,int v){
            if(!u) return v;
            push_d(u);
            if(!v) return u;
            push_d(v);
            if(d[u].key<d[v].key){
                d[u].s[1]=merge(d[u].s[1],v);
                upd(u);
                return u;
            }
            else{
                d[v].s[0]=merge(u,d[v].s[0]);
                upd(v);
                return v;
            }
        }
        void inorder_prt(int u){
            push_d(u);
            if(d[u].s[0]) inorder_prt(d[u].s[0]);
            printf("%d ",d[u].val);
            if(d[u].s[1]) inorder_prt(d[u].s[1]);
        }
    public:
        void build(int n,int a[]){
            static stack<int> stk;
            stk.push(0);
            for(int i=1,fa;i<=n;++i){
                d[i].val=a[i];
                d[i].key=rand();
                d[i].sz=1;
                while(fa=stk.top(),d[fa].key>d[i].key){
                    upd(fa);
                    stk.pop();
                }
                d[i].s[0]=d[fa].s[1];
                d[fa].s[1]=i;
                stk.push(i);
            }
            while(stk.size()>1){
                upd(stk.top());
                stk.pop();
            }
            stk.pop();
            rt=d[0].s[1];
        }
        void rvs(int l,int r){
            dual_rt x=split(rt,l-1);
            dual_rt y=split(x.rrt,r-l+1);
            d[y.lrt].rev^=true;
            rt=merge(merge(x.lrt,y.lrt),y.rrt);
        }
        void prt(){inorder_prt(rt);}
}T;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    tmp[i]=i;
    T.build(n,tmp);
    for(int i=1,l,r;i<=m;++i){
        scanf("%d%d",&l,&r);
        T.rvs(l,r);
    }
    T.prt();
    return 0;
}

[2017.9.9 NOIP模拟赛] 完整的海报

正解线段树区间合并，当时写挂调不出来了，灵机一动硬上了个非旋转式Treap...
建两棵Treap，分别维护完整海报的左端点和右端点；
记维护左端点的Treap为 $lp$ ，维护右端点的Treap为 $rp$ ；
对于每个新加入的海报记左端点为 $l$ ，右端点为 $r$ ；
则画图易得：被覆盖成不完整的海报数量 $=rp$ 中不小于 $l$ 的端点数量 $-lp$ 中大于 $r$ 的端点数量；
现在考虑怎么删除不完整的海报；
对于 $lp$ ，端点在区间 $(rp$ 中 $l$ 的前趋 $,r]$ 的一定不合法，要删除；
对于 $rp$ ，端点在区间 $[l,lp$ 中 $r$ 的后继 $)$ 的一定不合法，要删除；
由于以上删除的都是连续的一段值，所以Splay和非旋转式Treap都可以，但是感觉非旋转式Treap好写点而且快；
之后就是把 $l,r$ 分别插入即可；
如果不是很明白，自己按样例画个图模拟一下就看出来了。

代码：

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    x=0;
    int pm=1; char c;
    do{c=getchar();}while(!isdigit(c) && c!='-');
    c=='-' ? pm=-1:x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cstdlib>
#include <climits>
const int MAXN=200005;
int n,L,tt;
class FHQ_Treap{
    private:
        int rt,cnt;
        struct dual_rt{int lrt,rrt;};
        struct node{int ls,rs,val,key,sz;}d[MAXN];
        int new_nd(int val){
            d[++cnt].val=val;
            d[cnt].key=rand();
            d[cnt].sz=1;
            return cnt;
        }
        void upd(int u){
            d[u].sz=d[d[u].ls].sz+d[d[u].rs].sz+1;
        }
        dual_rt split(int u,int val){
            dual_rt ret=(dual_rt){0,0};
            if(!u) return ret;
            if(val<d[u].val){
                ret=split(d[u].ls,val);
                d[u].ls=ret.rrt;
                ret.rrt=u;
            }
            else{
                ret=split(d[u].rs,val);
                d[u].rs=ret.lrt;
                ret.lrt=u;
            }
            upd(u);
            return ret;
        }
        int merge(int u,int v){
            if(!u) return v;
            else if(!v) return u;
            if(d[u].key<d[v].key){
                d[u].rs=merge(d[u].rs,v);
                upd(u);
                return u;
            }
            else{
                d[v].ls=merge(u,d[v].ls);
                upd(v);
                return v;
            }
        }
        int kth_val(int u,int k){
            if(!k) return -1;
            while(true){
                if(k<=d[d[u].ls].sz) u=d[u].ls;
                else if(k>d[d[u].ls].sz+1){
                    k-=d[d[u].ls].sz+1;
                    u=d[u].rs;
                }
                else return d[u].val;
            }
        }
    public:
        void ist(int val){
            dual_rt x=split(rt,val);
            rt=merge(merge(x.lrt,new_nd(val)),x.rrt);
        }
        void del(int lval,int rval){
            dual_rt x=split(rt,lval);
            dual_rt y=split(x.rrt,rval-1);
            rt=merge(x.lrt,y.rrt);
        }
        int lge_cnt(int val){
            dual_rt x=split(rt,val);
            int ret=d[x.rrt].sz;
            rt=merge(x.lrt,x.rrt);
            return ret;
        }
        int geq_cnt(int val){
            dual_rt x=split(rt,val-1);
            int ret=d[x.rrt].sz;
            rt=merge(x.lrt,x.rrt);
            return ret;
        }
        int pred(int val){
            dual_rt x=split(rt,val-1);
            int ret=kth_val(x.lrt,d[x.lrt].sz);
            rt=merge(x.lrt,x.rrt);
            return ret==0 ? INT_MIN:ret;
        }
        int succ(int val){
            dual_rt x=split(rt,val);
            int ret=kth_val(x.rrt,1);
            rt=merge(x.lrt,x.rrt);
            return ret==0 ? INT_MAX:ret;
        }
}lp,rp;
inline int add(int l,int r){
    static int ret=0;
    ret-=rp.geq_cnt(l)-lp.lge_cnt(r);
    ++ret;
    lp.del(rp.pred(l),r+1);
    lp.ist(l);
    rp.del(l-1,lp.succ(r));
    rp.ist(r);
    return ret;
}
int main(){
    setIO("poster");
    read(L),read(n),read(tt);
    if(tt){
        for(int i=1,x,y,lastans=0;i<=n;++i){
            read(x),read(y);
            x^=lastans,y^=lastans;
            lastans=add(x,y);
            write(lastans,'\n');
        }
    }
    else{
        for(int i=1,x,y;i<=n;++i){
            read(x),read(y);
            write(add(x,y),'\n');
        }
    }
    return 0;
}

应用

作为普通的平衡树

支持平衡树的基本操作，还有Splay的区间操作（貌似只有LCT里的是真不行）；
速度比较优秀，而且十分好写好调试。

可持久化

由于非旋转式Treap是众多平衡树中少有的没有旋转操作的，所以每次操作后，其它未被操作的节点间父子关系不变，这就允许了它的可持久化（其它树操作一次结构都变了，咋可持久化？）；
学习笔记。