首页 📚学习笔记

Splay

作为一种可支持操作多,复杂度稳定,应用广泛的平衡树,Splay绝对是居家必备

作为一颗二叉查找树,他是通过不断旋转节点到根节点以此来保证平衡(而不至于退化到链)

旋转

首先我们需要知道如何旋转一个节点上去并且不会破坏二叉查找树的性质

现在假设我们要旋转的是$x$号节点

因为根据二叉查找树的性质,我们知道左子树的任意一个节点权值是小于等于这个点权值并且右子树是大于等于的

所以我们就可以旋转成

总结规律可知,如果我们要旋转的点$x$和他父亲&fa&的关系是&a&(左儿子或右儿子)

那么旋转完后,$fa$的$a$儿子就是$x$的$!a$儿子,$fa$就是$x$的&!a&儿子

inline void rotate(int x){
    int fa=f[x],gfa=f[fa],rel=getrel(x);
    son[fa][rel]=son[x][rel^1];
    f[son[fa][rel]]=fa;
    son[x][rel^1]=fa;
    f[fa]=x;f[x]=gfa;
    if(gfa)son[gfa][son[gfa][1]==fa]=x;
    update(fa);update(x);return;
 }

但是有时候如果一直转一个点,好像没什么变化

像这种情况,深度就只降了一层,所以我们发现,当$x$和他的父亲节点以及祖父节点是一条链时,我们先旋转父亲节点,再旋转$x$节点

实验证明,这样子可以更好地维护Splay的平衡性,更能使树的深度达到$\log n$

然后当我们做操作的时候,就把操作的那个数移上来,多旋转几次以维护树的平衡性,使得复杂度稳定在$\log n$上

Code

#include<bits/stdc++.h>
#define ls son[x][0]
#define rs son[x][1]
#define int long long
using namespace std;
const int N=2e5+9;
int son[N][2],val[N],sz[N],cnt[N],f[N],root,idx;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline int getrel(int x){
    return son[f[x]][1]==x;
}
inline void update(int x){
    if(!x)return;
    sz[x]=sz[ls]+sz[rs]+cnt[x];
}
inline void rotate(int x){
    int fa=f[x],gfa=f[fa],rel=getrel(x);
    son[fa][rel]=son[x][rel^1];
    f[son[fa][rel]]=fa;
    son[x][rel^1]=fa;
    f[fa]=x;f[x]=gfa;
    if(gfa)son[gfa][son[gfa][1]==fa]=x;
    update(fa);update(x);return;
}
inline void splay(int x){
    for(int fa;fa=f[x];rotate(x))
        if(f[fa])rotate(getrel(x)==getrel(fa)?fa:x);
    root=x;
}
inline void ins(int x){
    if(!root){
        root=++idx;
        val[idx]=x,cnt[idx]=1,sz[idx]=1;
        return;
    }
    int now=root,fa=0;
    while(1){
        if(x==val[now]){
            cnt[now]++,sz[now]++;
            update(fa);splay(now);break;
        }
        fa=now,now=son[now][x>val[now]];
        if(!now){now=++idx;
            f[idx]=fa,sz[idx]=cnt[idx]=1;
            son[fa][val[fa]<x]=idx;val[idx]=x;
            update(fa);splay(idx);break;
        }
    }return;
}
inline int find_rk(int x){
    int now=root,ans=0;
    while(1){
        if(x<val[now])now=son[now][0];
        else{
            ans+=sz[son[now][0]];
            if(x==val[now])return splay(now),ans+1;
            ans+=cnt[now];now=son[now][1];
        }
    }
}
inline int find_num(int x){
    int now=root,ans=0;
    while(1){
        if(sz[son[now][0]]>=x)now=son[now][0];
        else{
            x-=sz[son[now][0]];
            if(x<=cnt[now])return val[now];
            x-=cnt[now];now=son[now][1];
        }
    }
}
inline int find_pre(){
    int now=son[root][0];
    while(son[now][1])now=son[now][1];
    return now;
}
inline int find_suf(){
    int now=son[root][1];
    while(son[now][0])now=son[now][0];
    return now;
}
inline void del(int x){
    find_rk(x);
    if(cnt[root]>1)return cnt[root]--,update(root),void();
    if((son[root][0]|son[root][1])==0)return root=0,void();
    if(!son[root][0]){
        root=son[root][1];
        f[root]=0;return;
    }
    if(!son[root][1]){
        root=son[root][0];
        f[root]=0;return;
    }
    int l_max=find_pre();
    int odt=root;
    splay(l_max);
    son[root][1]=son[odt][1];
    f[son[odt][1]]=root;
    update(root);return;
    
}
signed main(){
    int m=read();
    while(m--){
        int op=read(),x=read();
        switch(op){
            case 1:ins(x);break;
            case 2:del(x);break;
            case 3:printf("%d\n",find_rk(x));break;
            case 4:printf("%d\n",find_num(x));break;
            case 5:ins(x);printf("%d\n",val[find_pre()]);del(x);break;
            case 6:ins(x);printf("%d\n",val[find_suf()]);del(x);break;
        }
    }
    return 0;
}

反转区间

在文艺平衡树这道题里,Splay还可以维护区间反转

如果反转的区间是$l~r$,我们就把$l-1$旋转到根节点,然后把&r+1&旋转到根节点右儿子

根据二叉查找树的性质可知,现在所有的&l~r&都在$r+1$的左儿子里面,所以我们只需要打一个标记,让所有的子树交换左右儿子即可,类似于线段树的方式

然后下次做操作前$push_down$一下

另外要多加两个节点$INF,-INF$以免旋转整个区间会出锅

#include<iostream>
#include<cstdio>
#define ls t[x].son[0]
#define rs t[x].son[1]
#define int long long
using namespace std;
const int N=2e5+9;
const int INF=1e9+7;
int rt,idx,a[N];
struct Splay_tree{
    int tag,sz,val,cnt,f;
    int son[2];
}t[N];
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline bool getrel(int x){
    return t[t[x].f].son[1]==x;
}
inline void update(int x){
    if(!x)return;
    t[x].sz=t[ls].sz+t[rs].sz+t[x].cnt;
}
inline void push_down(int x){
    if(x&&t[x].tag){
        t[ls].tag^=1;
        t[rs].tag^=1;
        swap(ls,rs);
        t[x].tag=0;
    }return;
}
inline void rotate(int x){
    int fa=t[x].f,gfa=t[fa].f;
    push_down(fa),push_down(x);
    bool rel=getrel(x);
    t[fa].son[rel]=t[x].son[rel^1];
    t[fa].f=x;
    t[t[fa].son[rel]].f=fa;
    t[x].son[rel^1]=fa;
    t[x].f=gfa;
    if(gfa)t[gfa].son[t[gfa].son[1]==fa]=x;
    update(fa);return;
}
inline void splay(int x,int top){
    for(int fa;(fa=t[x].f)!=top;rotate(x))
        if(t[fa].f!=top)
            rotate(getrel(x)==getrel(fa)?fa:x);
    if(top==0)rt=x;return;
}
int build(int l,int r,int fa){
    if(l>r)return 0;
    int mid=(l+r)>>1;
    int p=++idx;
    t[p].f=fa;t[p].cnt++;t[p].sz++;
    t[p].val=a[mid];
    t[p].son[0]=build(l,mid-1,p);
    t[p].son[1]=build(mid+1,r,p);
    update(p);
    return p;
}
inline int find(int x){
    int now=rt;
    while(1){
        push_down(now);
        if(x<=t[t[now].son[0]].sz)now=t[now].son[0];
        else{
            x-=t[t[now].son[0]].sz;
            if(x==1)return now;
            x--;now=t[now].son[1];
            
        }
    }
}
inline void reverse(int x,int y){
    int l=x-1,r=y+1;
    l=find(l),r=find(r);
    splay(l,0);splay(r,l);
    t[t[t[rt].son[1]].son[0]].tag^=1;
}
inline void dfs(int x){
    push_down(x);
    if(t[x].son[0])dfs(t[x].son[0]);
    if(t[x].val!=INF&&t[x].val!=-INF)
        printf("%lld ",t[x].val);
    if(t[x].son[1])dfs(t[x].son[1]);
}
signed main(){
    int n,m,x,y;
    n=read(),m=read();
    a[1]=-INF,a[n+2]=INF;
    for(int i=1;i<=n;i++)
        a[i+1]=i;
    rt=build(1,n+2,0);
    for(int i=1;i<=m;i++){
        x=read(),y=read();
        reverse(x+1,y+1);
    }    
    dfs(rt);
    return 0;
}



文章评论

目录