主要记录代码片段,以便于以后不会写的时候能回忆起来。

平衡树是要维护一棵二叉搜索树 BST,满足每个点(如果存在)的左子树都小于自己,右子树都大于自己。

Splay 就可以维护这样的一棵二叉搜索树。如果能让树高尽量的维持在 log 级别,那我们的操作就都是 $O(\log n)$ 的。

P3369 【模板】普通平衡树 为例。

son[x][0/1] 记录 $x$ 的左右儿子。f[x] 记录 $x$ 的父亲。

cnt[x] 表示 $x$ 结点值的出现次数。因为平衡树里的值需要各不相同,不然不能严格满足 BST 的性质。

sz[x] 表示 $x$ 的子树大小。num[x] 表示 $x$ 结点对应的权值。

ls:son[x][0],rs:son[x][1]

size 全局树大小, rt 即 root ,根。


函数定义:

基础函数 clear,get,update,init,link
  • clear(x):清空 x 点的所有信息。

    void clear(int x){
        f[x]=num[x]=sz[x]=cnt[x]=ls=rs=0;
    }
  • get(x):获取 x 点是父亲的 0/1 儿子。

    int get(int x){
        return son[f[x]][1]==x;
    }
  • update(x):更新 x 点的 sz 信息。

    void update(int x){
        sz[x]=cnt[x];
        if(ls)sz[x]+=sz[ls];
        if(rs)sz[x]+=sz[rs]; 
    }
  • init(x):新加入的点编号作为size,权值是x,更新这个点的信息。

    void init(int x){
        num[size]=x,sz[size]=cnt[size]=1,son[size][0]=son[size][1]=0;
    }
  • link(x,y,z):把 y 作为父亲,向 x 连一条关系为 z(0/1) 的边。

    void link(int x,int y,int z){//x<---z----y(fa)
        if(x)f[x]=y;if(y)son[y][z]=x;
    }

这么写的原因是,我们允许把根节点的父亲赋值为 0 ,但不能修改 0 结点的儿子信息。否则不小心遍历到 0 结点时意外访问可能陷入死循环


平衡重点 rotate,splay
  • rotate(x):把x点上旋。

这里的 n,m 描述的是 ffa->fa 和 fa->x 原本的边类型(连向左儿子或是右儿子),为了不影响平衡树的二叉搜索性质,我们就如图所示进行新的连边。

为什么这样不会影响它的二叉搜索性质呢?x 子树作为 fa 的 m 儿子,都满足同一个和 $num_{fa}$ 的大小关系。所以 S 自然可以成为 fa 的 m 儿子,而 x 要作为 fa 的父亲,大小关系就只能取反成为 m^1 。因为 x,fa 同属 ffa 的 n 子树,是 x 或是 fa 作为 ffa 的 n 儿子并没有影响,所以这样旋转即可。

void splay(int x){
    for(int fa=f[x];fa;rotate(x),fa=f[x])
        if(f[fa])rotate(get(x)==get(fa)?fa:x);
    rt=x;
}
  • splay(x,to):把 x 结点旋转到 to 结点下方,常用的 to 即 0 ,即把 x 旋转到根节点的位置。

这个操作是为了保证平衡树的树高基本位置在 $\log$ 级别。那么考虑怎么把一个点向上旋转可以尽可能保证树的平衡。

如果朴素地一路 rotate 最后的结果就只能是这样。于是我们就可以 只当结点 x 和 fa , fa 和 ffa 连续两条边都是同一类型(都连向左或都连向右时),先 rotate(fa),再 rotate(x) 。这样就可以旋转出漂亮的复杂度。

void splay(int x,int to=0){
    for(int fa=f[x];fa!=to;rotate(x),fa=f[x])
        if(f[fa]!=to)rotate(get(x)==get(fa)?fa:x);
    if(to==0)rt=x;
}

维护序列 insert,find,kth,pre,nxt,del
  • insert(k):插入一个权值为 k 的结点。

如果没有根,那新建结点作为根 rt=++sizeinit(k)

否则 while 找到自己的位置。

如果找到和 x 点有一样的权值,那就 cnt[x]++,update(x),update(fa),splay(x) ,随手 splay 是为了保证复杂度。

fa=x,x=son[x][k>num[x]] 根据值判断向左还是向右走。

如果走到空节点,说明在这里新建即可。

if(!x)return size++,init(k),f[size]=fa,son[fa][k>num[fa]]=size,update(fa),splay(size),void();

void insert(int k){
    if(!rt)return rt=++size,init(k),void();
    int x=rt,fa=0;
    while(1){
        if(num[x]==k)return cnt[x]++,update(x),update(fa),splay(x),void();
        fa=x,x=son[x][k>num[x]];
        if(!x)return size++,init(k),
        f[size]=fa,son[fa][k>num[fa]]=size,update(fa),splay(size),void();
    }
}
  • find(k):找到数值 k 对应的排名。这里排名指小于 k 的数的数量。

从根开始,while 找位置。如果 k 比当前 x 结点权值要小,那就向左子树走,直到有大于等于结点 x 的权值时。此时 k 大于所有左子树的元素,ans+=sz[ls],如果找到 num[x]==k ,那当前记录的 ans 就是答案。否则 ans+=cnt[x],x=rs

int find(int k){
    int x=rt,ans=1;
    while(1){
        if(k<num[x]){x=ls;continue;}
        ans+=sz[ls];
        if(k==num[x])return splay(x),ans;
        ans+=cnt[x],x=rs;
    }
}
  • kth(k):找到排名 k 对应的数值。

从根开始,while 找位置。如果 k 小于等于当前左子树的 sz,就向左子树走,直到 k 大于左子树的 sz,此时答案一定不在左子树中。k-=sz[ls],并且如果 k<=cnt[x],那就可以在 x 点停下,因为 x 点对应的权值就是返回的答案。否则 k-=cnt[x],x=rs 继续向右子树走。

int kth(int k){
    int x=rt;
    while(1){
        if(k<=sz[ls]){x=ls;continue;}
        if(ls)k-=sz[ls];
        if(k<=cnt[x])return splay(x),num[x];
        k-=cnt[x],x=rs;
    }
}
  • pre(),nxt():找前驱,后继。

先把要找前驱后继的值插入,插入之后自然 splay 到根,然后根据二叉搜索树的性质做即可。

int pre(){
    int now=son[rt][0];while(son[now][1])now=son[now][1];return now;
}
int nxt(){
    int now=son[rt][1];while(son[now][0])now=son[now][0];return now;
}
  • del(x):删除 x 值对应的节点。

先 find(x) ,返回的值不重要,但这会把对应的结点自然 splay 到根节点 rt 。

1.如果 cnt[rt]>1cnt[rt]--,update(rt);return; 即可。

2.如果左右儿子都不存在,那直接把这个点 clear 了即可。

3.如果左/右儿子不存在,那就把右/左儿子作为根即可。

4.找到前驱 l ,把它 splay 到根,再把它连向原来的右儿子,clear,return 即可。

void del(int x){
    find(x);int tmp=rt;
    if(cnt[rt]>1)return cnt[rt]--,update(rt),void();
    if(!son[rt][0]&&!son[rt][1])return clear(rt),rt=0,void();
    if(!son[rt][0])return f[rt=son[rt][1]]=0,clear(tmp),void();
    if(!son[rt][1])return f[rt=son[rt][0]]=0,clear(tmp),void();
    int l=pre();splay(l),link(son[tmp][1],rt,1),clear(tmp),update(rt);
}

完整代码Link


Splay 维护区间问题

P3391 【模板】文艺平衡树

序列长度为 $n$ ,数值初始为 $1$ ~ $n$ ,$m$ 个操作,把区间 $[l_i,r_i]$ 翻转,求输出最终序列。

显然对于每个点它初始的权值是 $i$ ,我们考虑把输入的 l,r 都加一,就变成维护初始为 $[2,n+1]$ 的序列了。可以先递归建树,然后每次翻转相当于把只有 $[l,r]$ 的子树里每个点的左右儿子翻转,于是 splay(find(r+1),0),splay(find(l-1),find(r+1)) 再打标记即可。

完整代码Link

最后修改:2021 年 03 月 25 日 07 : 54 PM