柒葉灬 的博客

柒葉灬 的博客

splay总结(个人笔记)

posted on 2019-02-10 16:50:04 | under 专题总结 |

splay总结


$splay$ 本质上是一棵平衡树,

但是用上了 $splay$ 算法之后他可以使深度接近 $log$

核心函数有下面两个:

  1. 翻转节点 $x$ , $rotate$
  2. 把节点 $x$ 变成 $goal$ 的儿子, $splay$

代码:

int rt,tot,val[maxn],fa[maxn],son[maxn][2],sz[maxn];
void up(int x){
    sz[x]=sz[son[x][0]]+sz[son[x][1]]+1;
}
void rotate(int x){
    int y=fa[x];
    int z=fa[y];
    int k=(son[y][1]==x);
    son[z][(son[z][1]==y)]=x;
    fa[x]=z;
    son[y][k]=son[x][k^1];
    fa[son[x][k^1]]=y;
    son[x][k^1]=y;
    fa[y]=x;
    up(y);up(x);
}
void splay(int x,int goal){
    while(fa[x]!=goal){
        int y=fa[x];
        int z=fa[y];
        if(z!=goal)
            (son[z][1]==y)^(son[y][1]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0)rt=x;
}

插入操作 1:

(注意,这里的插入操作是没有重复元素的情况)

void insert(int x){
    int u=rt,f=0;
    while(u){
        f=u;
        u=son[u][x>val[u]];
    }
    u=++tot;
    fa[tot]=f;
    son[f][x>val[f]]=tot;
    val[tot]=x;
    sz[tot]=1;
    splay(tot,0);
}

插入操作 2:

但是往往插入的时候不是按照权值来插入,而是按照编号

这时候就用下列的方法即可。

void insert(int x){
    val[++tot]=x;
    fa[tot]=tot-1;
    son[tot-1][1]=tot;
    sz[tot]=1;
    splay(tot,0);
}

查找前驱和后继

( $0$ 表示找前驱, $1$ 表示找后继)

int Next(int x,int type){
    splay(x,0);
    if(!son[rt][type])return -1;
    int u=son[rt][type];
    while(son[u][type^1])
        u=son[u][type^1];
}

查找第 $K$ 大元素

int find(int K){
    int u=rt;
    while(true){
        if(sz[son[u][0]]>=K)u=son[u][0];
        else if(sz[son[u][0]]+1==K)return u;
        else K-=sz[son[u][0]]+1,u=son[u][1];
    }
}

删除节点操作

void del(int x){
    splay(x,0);
    if(!son[x][0]||!son[x][1]){
        int tmp=(son[x][0]|son[x][1]);
        fa[tmp]=0;
        rt=tmp;
        return;
    }
    int u=Next(rt,1);
    son[u][0]=son[rt][0];
    fa[son[rt][0]]=u;
    rt=son[rt][1];
    fa[son[rt][1]]=0;
    splay(u,0);
}

技巧1. 区间修改操作

在 $splay$ 树中加两个虚点,一个头一个尾。

(保证每一个点都有前驱和后继)

比如说现在需要修改 $ [l,r] $ 这个区间,

代码:

void update(int l,int r){
    int lx=find(l);
    int rx=find(r+2);
    splay(lx,0);
    splay(rx,lx);
    change(son[rx][0]);
}

因为一开始在头有一个虚点,所以修改的区间应该是 $[l+1,r+1]$

找到 $l+1$ 的前驱 $lx$ -> $find(l)$

以及 $r+1$ 的后继 $rx$ -> $find(r+2)$

那么 $son[rx][0]$ 就是我们要修改的区间了。


技巧2. 当做线段树使用

$splay$ 可以当做线段树一样维护一个区间的信息

比如说区间求和,最大连续和之类的。

详细见 splay专题 I


使用细节(重点!!)

一定要尽量用 $splay$ 操作,

不能出现找到一个点之后不 $splay$ 的情况

否则很有可能被卡 T 掉。

$splay$ 的复杂度是均摊的,是有了 $splay$ 操作才能均摊,

否则复杂度玄学。(出题人可以卡)

详细见splay专题 J


注意那种修改操作,打 $lazy$ 标记的那种

一定是先修改节点信息再打标记

一定注意不能在 $down$ 的时候才修改!!!