fhq treap——无旋treap

●前置知识：二叉排序树 treap 了解什么是函数式编程

●本文代码均未经编译，如有错误请指出。

●QQ826755370

引入

-“平衡树好烦啊，转来转去的，而且treap遇到区间序列问题就gg。”

-“有一种不用旋转的treap，叫fhq treap，可以解决区间序列问题。”

正文

约定

我们做出以下约定：

int ch[MAXN][3];//0 左孩子，1右孩子
int val[MAXN];//每个点的权值
int rnd[MAXN];//每个点的随机权值
int size[MAXN];//以每个点为根的树的大小

分裂

分裂有两种，一种是权值分裂，一种是排名分裂。我们先讲权值分裂。如图，当我们遍历到一个节点时，如果它的权值小于k，那么它的左子树会被分到左边的树里，然后我们遍历它的右儿子，如果大于k，则把它的右子树分到右边的树里。如果到达递归边界now==0怎么办呢？这里会有两种情况：

1.root=0（即第一次split），很明显要给x和y初始化，即x=y=0。

2.split到了叶子节点，此时无法继续split了，只能返回。此时的x=y=0没什么用，因为x和y会在回溯的时候通过地址符号改变。

代码：

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);//update(i)为更新size[i]大小的函数
}

排名分裂与权值分裂类似，即将前k个放在一颗树里，其余的放在另一棵树里。代码：

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

合并

如图，我们假设第一棵树的权值小于第二棵树的权值，那么我们就比较它们的随机权值。如果rnd[l]<rnd[r]，我们就保留它的左子树，另一棵树作为它的右子树；如果rnd[l]>=rnd[r]，那我们可以保留第二棵树的右子树，另一颗树作为它的左子树。代码：

int merge(int A,int B)
{
    if(!A||!B)
        return A+B;
    if(rnd[A]<rnd[B])
    {
        ch[A][1]=merge(ch[A][1],B);
        update(A);
        return A;
    }
    else
    {
        ch[B][0]=merge(A,ch[B][0]);
        update(B);
        return B;
    } 
}

以上操作完成后，我们就可以用函数式编程的思想完成剩余的操作。

插入

直接暴力merge，代码：

int new_node(int a)//新建一个节点
{
    size[++cnt]=1;
    val[cnt]=a;
    rnd[cnt]=rand();
    return cnt;
}
void insert(int a)//插入 
{
    spilt(root,a,x,y);
    root=merge(merge(x,new_node(a)),y);
}

删除

删除权值为v的点，先把整颗树以v为权值split成两棵树a,b,再把a树按照v-1分成c,d。这时候值为v的点一定为d的根，那么我们把d的两个子儿子merge起来（划重点：这一步就是去除掉v的影响），再把他们重新merge起来得到一个新的树，这颗树就去除掉了v的影响。代码：

void del(int a)
{
    split(root,a,x,z);
    split(x,a-1,x,y);
    y=merge(ch[y][0],ch[y][1]);
    root=merge(merge(x,y),z);
}

排名

直接按照a-1的权值把树分开，那么x树中最大的应该小于等于a-1，那么a的排名就是size[x]+1。代码：

int myrank(int a)
{
    split(root,a-1,x,y);
    int res=size[x]-1;
    root=merge(x,y);
    return res;
}

k小值

不想说什么，直接看代码：

int findKth(int k)
{
    return val[myrank(root,k)];
}

前驱后继

我们先看前驱，因为要小于a，所以我们还是按照a-1的权值划分x，现在x中最大的数一定小于等于a-1，所以我们直接输出x中最大的数就好，后继同理，不再赘述。代码：

int pre(int a)
{
    split(root,a-1,x,y);
    int res=val[findKth(x,siz[x])];
    root=merge(x,y);
    return res;
}
int nxt(int a)
{
    split(root,a,x,y);
    int res=val[findKth(y,1)];
    root=merge(x,y);
    return res;
}

关于区间问题

查询一个区间[l, r]就把一棵树split成三棵树，查中间那棵，再把它们merge回去。代码：

void add(int l,int r,int delta)//任意操作 
{
    int x,y,z;
    split(root,x,y,r);
    split(x,z,x,l-1);
    addone(x,delta);//任意操作 
    merge(x,z,x);
    merge(root,x,y);
}

关于可持久化

fhq treap可以可持久化。如图，每次split和merge走到的所有点都新建一个即可。注意下传标记也要新建点。

三道裸题

1.洛谷P3369 普通disco平衡树

就是把上面的东西综合在一起。代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>

#define maxn 500001

using 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]<fix[B]){ch[A][1]=merge(ch[A][1],B); update(A); return A;}
    else {ch[B][0]=merge(A,ch[B][0]); update(B); return B;} 
}

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);
    }
}

int kth(int now,int k)
{
    while(1)
    {
        if(k<=size[ch[now][0]]) now=ch[now][0];
        else if(k==size[ch[now][0]]+1) return now;
        else k-=size[ch[now][0]]+1,now=ch[now][1];
    }
}

int main()
{
    srand((unsigned)time(NULL));
    T=read();
    while(T--)
    {
        p=read();a=read();
        if(p==1)
        {
            split(root,a,x,y);
            root=merge(merge(x,new_node(a)),y);
        }
        else if(p==2)
        {
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(ch[y][0],ch[y][1]);
            root=merge(merge(x,y),z);
        }
        else if(p==3)
        {
            split(root,a-1,x,y);
            printf("%d\n",size[x]+1);
            root=merge(x,y);
        }
        else if(p==4) printf("%d\n",val[kth(root,a)]);
        else if(p==5)
        {
            split(root,a-1,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,1)]);
            root=merge(x,y);
        }
    }
    return 0;
}

本题还有一种树状数组解法：树状数组解法。

2.洛谷P3391 文艺平衡树。

区间操作。代码（感谢守望的代码）：

# include<iostream>
# include<cstdio>
# include<cstring>
# include<cstdlib>
using namespace std;
const int MAX=1e5+1;
int n,m,tot,rt;
struct Treap{
    int pos[MAX],siz[MAX],w[MAX];
    int son[MAX][2];
    bool fl[MAX];
    void pus(int x)
    {
        siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
    }
    int build(int x)
    {
        w[++tot]=x,siz[tot]=1,pos[tot]=rand();
        return tot;
    }
    void down(int x)
    {
        swap(son[x][0],son[x][1]);
        if(son[x][0]) fl[son[x][0]]^=1;
        if(son[x][1]) fl[son[x][1]]^=1;
        fl[x]=0;
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x+y;
        if(pos[x]<pos[y])
        {
            if(fl[x]) down(x);
            son[x][1]=merge(son[x][1],y);
            pus(x);
            return x;
        }
        if(fl[y]) down(y);
        son[y][0]=merge(x,son[y][0]);
        pus(y);
        return y;
    }
    void split(int i,int k,int &x,int &y)
    {
        if(!i)
        {
            x=y=0;
            return;
        }
        if(fl[i]) down(i);
        if(siz[son[i][0]]<k)
        x=i,split(son[i][1],k-siz[son[i][0]]-1,son[i][1],y);
        else
        y=i,split(son[i][0],k,x,son[i][0]);
        pus(i);
    }
    void coutt(int i)
    {
        if(!i) return;
        if(fl[i]) down(i);
        coutt(son[i][0]);
        printf("%d ",w[i]);
        coutt(son[i][1]);
    }
}Tree;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
      rt=Tree.merge(rt,Tree.build(i));
    for(int i=1;i<=m;i++)
      {
          int l,r,a,b,c;
          scanf("%d%d",&l,&r);
          Tree.split(rt,l-1,a,b);
        Tree.split(b,r-l+1,b,c);
        Tree.fl[b]^=1;
        rt=Tree.merge(a,Tree.merge(b,c));
      }
    Tree.coutt(rt);
    return 0;
}

3.可持久化序列

可持久化序列这道题要求支持三个操作：

1 l r，翻转l到r的区间；

2 l r，询问l的到r的区间和；

3 p，回到p时刻。

每次修改新建点打翻转标记即可，代码（感谢permui的代码）：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> Pair;
int read() {
    int x=0,f=1;
    char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=5e4+5;
const int nlogn=1.3e7+5;
struct node {
    int x,hp,l,r,sum,size;
    bool rev;
    void clear() {
        x=hp=l=r=sum=size=rev=0;
    }
};
struct TREAP {
    int pool[nlogn];
    int pooler;
    node t[nlogn];
    int now,all;
    int root[maxn];
    TREAP ():now(0),pooler(1) {
        for (int i=1;i<nlogn;++i) pool[i]=i;
        root[now]=pool[pooler++];
    }
    int newroot() {
        int ret=pool[pooler++];
        return ret;
    }
    int newnode(int x) {
        int ret=pool[pooler++];
        t[ret].hp=rand();
        t[ret].size=1;
        t[ret].x=t[ret].sum=x;
        return ret;
    }
    void delnode(int x) {
        t[x].clear();
        pool[--pooler]=x;
    }
    void next() {
        root[++all]=newroot();
        t[root[all]]=t[root[now]];
        now=all;
    }
    void back(int x) {
        now=x;
    }
    void update(int x) {
        t[x].sum=t[x].x+t[t[x].l].sum+t[t[x].r].sum;
        t[x].size=t[t[x].l].size+t[t[x].r].size+1;
    }
    void pushdown(int x) {
        if (!t[x].rev) return;
        if (t[x].l) {
            int tx=newnode(t[t[x].l].x);
            t[tx]=t[t[x].l];
            t[tx].rev^=true;
            t[x].l=tx;
        }
        if (t[x].r) {
            int tx=newnode(t[t[x].r].x);
            t[tx]=t[t[x].r];
            t[tx].rev^=true;
            t[x].r=tx;
        }
        swap(t[x].l,t[x].r);
        t[x].rev=false;
    }
    int merge(int x,int y) {
        if (!x) return y;
        if (!y) return x;
        int now;
        if (t[x].hp<=t[y].hp) {
            now=newnode(t[x].x);
            t[now]=t[x];
            pushdown(now);
            t[now].r=merge(t[now].r,y);
        } else {
            now=newnode(t[y].x);
            t[now]=t[y];
            pushdown(now);
            t[now].l=merge(x,t[now].l);
        }
        update(now);
        return now;
    }
    Pair split(int x,int p) {
        if (t[x].size==p) return make_pair(x,0);
        int now=newnode(t[x].x);
        t[now]=t[x];
        pushdown(now);
        int l=t[now].l,r=t[now].r;
        if (t[l].size>=p) {
            t[now].l=0;
            update(now);
            Pair g=split(l,p);
            now=merge(g.second,now);
            return make_pair(g.first,now);
        } else if (t[l].size+1==p) {
            t[now].r=0;
            update(now);
            return make_pair(now,r);
        } else {
            t[now].r=0;
            update(now);
            Pair g=split(r,p-t[l].size-1);
            now=merge(now,g.first);
            pushdown(now);
            return make_pair(now,g.second);
        }
    }
    void rever(int l,int r) {
        ++l,++r;
        Pair g=split(root[now],l-1);
        Pair h=split(g.second,r-l+1);
        int want=h.first;
        int here=newnode(t[want].x);
        t[here]=t[want];
        t[here].rev^=true;
        int fi=merge(g.first,here);
        int se=merge(fi,h.second);
        root[now]=se;
    }
    int query(int l,int r) {
        ++l,++r;
        Pair g=split(root[now],l-1);
        Pair h=split(g.second,r-l+1);
        int want=h.first;
        int ret=t[want].sum;
        int fi=merge(g.first,want);
        int se=merge(fi,h.second);
        root[now]=se;
        return ret;
    }
    void insert(int x) {
        int k=newnode(x);
        root[now]=merge(root[now],k);
    }
} Treap;
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("my.out","w",stdout);
#endif
    srand(time(0));
    int n=read(),m=read();
    for (int i=1;i<=n;++i) {
        int x=read();
        Treap.insert(x);
    } 
    while (m--) {
        int op=read();
        if (op==1) {
            Treap.next();
            int l=read(),r=read();
            Treap.rever(l,r);
        } else if (op==2) {
            int l=read(),r=read();
            int ans=Treap.query(l,r);
            printf("%d\n",ans);
        } else if (op==3) {
            Treap.back(read());
        }
    }
    return 0;
}

作业

1.洛谷P2596 书架

2.洛谷P4309 最长上升子序列

3.洛谷P3987 我永远喜欢珂朵莉~

4.洛谷P3920 紫荆花之恋（在做此题前，你需要掌握点分治，你还需要一点替罪羊树的思想，不难，就是当一个点过于不平衡时，我们就拍掉重建）。

完结撒花！★,°:.☆(￣▽￣)/$:.°★ 。