djwj233 的博客

djwj233 的博客

Splay学习笔记

posted on 2021-08-05 19:17:57 | under 笔记 |

Splay 的用途

Splay 是一种平衡树,因此:

Splay 的原理

Splay 是一种通过旋转维护平衡的平衡树。

不同于 Treap 等树的是,Splay 每次操作都要把需要操作的结点旋转到根上,这使它的旋转异常复杂。

再丢出这张窝自制的图

这是 Treap 进行旋转的方法,被称为单旋

这里借一张Menci 博客里的图,表示 Splay 中的单旋。

单旋 $\texttt{rotate(x)}$ 的过程:(这里以右旋为例)

  • 自己连到祖父($\texttt{a[a[x].fa].fa}$)上;
  • 将自己的右儿子连到原先的父亲上(也就是替代了自己);
  • 父亲连到自己上(也就是替代了右儿子)
void Splay::rotate(int x) {
    int f=a[x].fa, c=which(x);
    a[a[f].fa].ch[which(f)]=x, a[x].fa=a[f].fa;
    a[f].ch[c]=a[x].ch[c^1], a[a[x].ch[c^1]].fa=f;
    a[x].ch[c^1]=f, a[f].fa=x;
    update(f), update(x); //注意一定要先更新f再更新x
}

但是,如果维护 Splay 只采用单旋是不对的,考虑原树是一条单链的情况,如果我们每次访问链最底部的一个点把它转到根,那么时间复杂度将会达到 $\Theta(n^2)$。

(实际上,单旋 Splay 被称为 Spaly,是假算法,在HNOI2017中出现过)

那么,Splay 的双旋应运而生。简单地说,双旋就是先单旋一次父亲、再单旋一次自己

如果我们的目标是把 $x$ 转上去,那么双旋的处理分为以下的六种情况:(图源 OI-wiki)

  • 1/2 两种只需一次单旋 $\texttt{rotate(x)}$ 即可完成。
  • 3/4 两种需要两次相同方向、不同节点的单旋 $\texttt{rotate(y)}$,$\texttt{rotate(x)}$ $\texttt{}$,被称为一字型旋转
  • 5/6 两种需要两次不同方向、相同节if(a[f].fa) if(a[f].fa) if(a[f].fa) 点的单旋 $\texttt{rotate(x)}$,$\texttt{rotate(x)}$,被称为之字型旋转

现在引入 $\texttt{splay(x)}$ 操作为通过一系列双旋将 $x$ 移到 $root$ 处。(此操作在中文中被称为伸展,这也是 Splay 中文名伸展树的由来)

void Splay::splay(int x) {
    for( int f=a[x].fa ; f ; f=a[x].fa ) {
        if(a[f].fa) rotate( which(x)==which(f) ? f : x );
        rotate(x);
    } rt=x;
}

最后一定要注意每次操作后必须 $\texttt{splay}$ !!!

(时间复杂度分析放在基本操作之后)

Splay 的基本操作

这里依旧以P3369 【模板】普通平衡树为例。

  • 单个结点

我们采取ch[0/1]的方式分别代表结点的左儿子、右儿子,并记录了每个结点的父亲。

struct node {
    int fa,ch[2];
    int val;
    int siz,cnt;
} a[N]; int tot,rt;
  • 更新结点信息与基本操作

    $\texttt{which}$ 操作询问了 $x$ 是其父亲的左结点还是右结点,这可以大大减少代码量。

int Splay::New(int v) {
    a[++tot].val=v, a[tot].siz=a[tot].cnt=1;
    return tot;
}
void Splay::update(int x) {
    a[x].siz=a[a[x].ch[0]].siz+a[a[x].ch[1]].siz+a[x].cnt;
}
int Splay::which(int x) {    return a[a[x].fa].ch[1]==x;    }
  • 单旋与双旋(重点)

见上。

  • 插入

注意不能在第 12 行后 $\texttt{splay}$,否则会变成递归地把每个结点旋到根。

然后因为 $\texttt{splay}$ 的过程中已经 $\texttt{update}$ 过所有结点了,因此最后不用再 $\texttt{update}$。

void Splay::insert(int &x,int f,int v)
{
    if(x==0) {
        x=New(v), a[x].fa=f;
        splay(x); return ;
    }
    if(v<a[x].val) insert(a[x].ch[0],x,v);
    else if(v==a[x].val) {
        a[x].cnt++, splay(x);
        return ;
    }
    else insert(a[x].ch[1],x,v);
}
  • 查值与查排名
int Splay::getRank(int x,int v)
{
    if(x==0) return 1;
    if(v<a[x].val) return getRank(a[x].ch[0],v);
    else if(v==a[x].val) {
        int res=a[a[x].ch[0]].siz+1;
        splay(x); return res;
    } else {
        int res=a[a[x].ch[0]].siz+a[x].cnt;
        return res+getRank(a[x].ch[1],v);
    }
}
int Splay::getVal(int x,int v)
{
    if(x==0) {
        splay(x); return a[x].val;
    }
    if(v<=a[a[x].ch[0]].siz) return getVal(a[x].ch[0],v);
    else if(v<=a[a[x].ch[0]].siz+a[x].cnt) {
        splay(x); return a[x].val;
    } else return getVal(a[x].ch[1],v-a[a[x].ch[0]].siz-a[x].cnt);
}
  • 查前驱、后继

以前驱为例,我们可以通过新插入一个结点,查前驱,再删除的方式。

对已经在树中的结点查前驱十分方便,只需 $\texttt{splay}$ 后在左子树中向右走到底即可。

int Splay::getPre() {
    int p=a[T.rt].ch[0];
    while(a[p].ch[1]) p=a[p].ch[1];
    splay(p); return p;
}
int Splay::getNxt() {
    int p=a[T.rt].ch[1];
    while(a[p].ch[0]) p=a[p].ch[0];
    splay(p); return p;
}

主函数中:

T.insert(T.rt,0,x);
printf("%d\n",T.a[T.getPre()].val);
T.erase(x);
  • 删除(重点)

我们先把要删除的结点 $\texttt{splay}$ 到根(这可以用一次 $\texttt{getRank}$ 实现),然后:

  1. 如果其 $cnt$ 值不小于 $2$,直接减去 $1$,然后 $\texttt{update}$;

  2. 否则,如果它没有左儿子或没有右儿子,则直接用另一个儿子替换它;

  3. 否则,将其左右儿子的两棵子树合并

    那么怎么合并呢?我们把左子树中最大的数 $\texttt{splay}$ 上来当作新的根,那么原来的根一定在新根的右儿子处,直接将它删去即可。

void Splay::erase(int v){    getRank(T.rt,v);    if(a[T.rt].cnt>1) {        a[T.rt].cnt--, update(T.rt);        return ;    }    if(a[T.rt].ch[0]==0) {        T.rt=a[T.rt].ch[1], a[T.rt].fa=0;        return ;    }    if(a[T.rt].ch[1]==0) {        T.rt=a[T.rt].ch[0], a[T.rt].fa=0;         return ;    }    int cur=T.rt, x=getPre();    a[a[cur].ch[1]].fa=T.        rt;    a[x].ch[1]=a[cur].ch[1];    update(x);}

Splay 的时间复杂度

事实上,我们可以证明:Splay 单次操作的时间复杂度是 $\mathcal O(\log n)$ 的

一些定义与约定

由于每次操作后都要把结点 $\texttt{splay}$ 到根,因此在操作中访问的结点都会在 $\texttt{splay}$ 中被再次访问。因此,操作的复杂度和旋转的复杂度相同。

我们记 $|x|$ 为以 $x$ 为根的子树的大小(为区分,后文有时用 $siz(x)$ 代替),并记 $n=|root|$。

记 $\Phi$ 为整棵 Splay(记为 $T$)的势能函数,$\phi(x)$ 为单个结点的所具有的势能。定义:$$ \phi(x)=\log |x|,\ \Phi=\sum\limits_{i=1}^n \phi(x) $$ 可以发现,对任意点 $x$ 有 $|x|\le n$,因此 $\Phi\le \sum_{i=1}^n \log n=n\log n$。

另外,我们在这里认为:单次 $\texttt{rotate}$ 的时间复杂度恒为 $\mathcal O(1)$

单旋

由于 $\texttt{zag}$ 和 $\texttt{zig}$ 相类似,我们这里只分析 $\texttt{zig}$ 的复杂度。

我们设当前要进行操作的点为 $x$,其父亲为 $y$。如下图:(图是自己做的,巨丑)

我们令旋转之后二者的势能分别为 $\phi^\prime(x),\phi^\prime(y)$,那么我们有:$$ \Delta\Phi=\phi^\prime(x)+\phi^\prime(y)-\phi(x)-\phi(y) $$ 由于转完后,$\textrm{subtree}^\prime(x)$ 包含了原先 $\textrm{subtree}(y)$ 中所有的结点,因此有 $\phi^\prime(x)=\phi(y)$;

又因为转完后 $y$ 是 $x$ 的子节点,因此 $siz^\prime(y)\le siz^\prime(x)$,可知 $\phi^\prime(y)\le \phi^\prime(x)$;

代入上式可得:$$ \Delta\Phi\le\mathcal O(1)+\phi^\prime(x)-\phi(x) $$

一字型旋转

同上,由于 $\texttt{zag-zag}$ 和 $\texttt{zig-zig}$ 相类似,我们这里只分析 $\texttt{zig-zig}$ 的复杂度。

同样,我们设当前要进行操作的点为 $x$,其父亲为 $y$,祖父为 $z$。

由于一字型旋转涉及两次 $\texttt{rotate}$,因此有:$$ \Delta\Phi=\mathcal O(1)+\phi^\prime(x)+\phi^\prime(y)+\phi^\prime(z)-\phi(x)-\phi(y)-\phi(z) $$ 模拟旋转过程有:

  • $\phi^\prime(x)=\phi(z)$;
  • $\phi^\prime(z)\le\phi^\prime(y)\le\phi^\prime(x)$;
  • $\phi(z)\ge\phi(y)\ge\phi(x)$。

代入:$$ \Delta\Phi\le \mathcal O(1)+2(\phi^\prime(x)-\phi(x)) $$ 但是,这个上界是不精准的,因为我们在下面求和时如果把这个 $\mathcal O(1)$ 带进去会炸掉。怎么办呢?

我们退回一步,并忽略 $2$ 这个常系数:$$ \Delta \Phi\le \mathcal O(1)+\phi^\prime(x)+\phi^\prime(z)-2\phi(x) $$

  • 引理:$\phi(x)+\phi^\prime(z)-2\phi^\prime(x)<-1$

证明:即证 $\log siz(x)+\log siz^\prime(z)-2\log siz^\prime(x)<-1$,也即 $\log \dfrac{siz(x)siz^\prime(z)}{siz^\prime(x)^2}<-1$。

画出旋转的图示,我们发现旋转前后 $\operatorname{subtree}_x$ 和 $\operatorname{subtree}^\prime_z$ 不相交且不包含点 $y$,即 $siz(x)+siz^\prime(z)<siz^\prime(x)$。

由 $\log$ 的单调性,$\log \dfrac{siz(x) siz^\prime(z)}{siz^\prime(x)^2}<\log \dfrac{siz(x)siz^\prime(z)}{(siz(x)+siz^\prime(z))^2}\le\log \dfrac{1}{2}\le-1$。证毕。

两式相加可得:$$ \Delta\Phi\le \mathcal O(1)\ {\color{red}{-1}}+\phi^\prime(x)-\phi(x) $$ 然后我看到的证明里都说 $\mathcal O(1)-1$ 能约掉,我也不知道是啥/yiw

总之我们有:$$ \Delta\Phi\le \phi^\prime(x)-\phi(x) $$

之字形旋转

这里只分析 $\texttt{zig-zag}$,并设当前要进行操作的点为 $x$,其父亲为 $y$,祖父为 $z$。

同上有:$$ \Delta\Phi=\mathcal O(1)+\phi^\prime(x)+\phi^\prime(y)+\phi^\prime(z)-\phi(x)-\phi(y)-\phi(z) $$

$$ \Delta \Phi\le \mathcal O(1)+\phi^\prime(x)+\phi^\prime(z)-2\phi(x) $$

但是,在引理 $\phi(x)+\phi^\prime(z)-2\phi^\prime(x)<-1$ 的证明中,$siz(x)+siz^\prime(z)<siz^\prime(x)$ 性质并不成立,我们需要找一个性质别的换掉

(图源这篇博客,其中 $p,g$ 分别等价于本文中的 $y,z$)

观察可知,可以把它换为 $siz^\prime(x)>siz^\prime(y)+siz^\prime(z)$,那么可得:$$ \phi^\prime(y)+\phi^\prime(z)-2\phi^\prime(x)<-1 $$ 因此,我们不应该像上面那样代入,应换成:$$ \Delta \Phi\le \mathcal O(1)+\phi^\prime(y)+\phi^\prime(z)-2\phi(x) $$ 这样就能推出:$$ \Delta\Phi\le \phi^\prime(x)-\phi(x) $$

总结

通过以上的证明,我们得到:对所有的点 $x$ 进行 $\texttt{rotate}$ 操作,其消耗的势能不大于 $\phi^\prime(x)-\phi(x)$。

因此,设一次 $\texttt{splay}$ 中涉及的点从浅到深为 $x_{1\cdots m}$,那么它的总复杂度为:$$ \mathcal O(1)+\sum\limits_{i=2}^m (\phi^\prime(x_i)-\phi(x_i)) $$ 其中,前面的 $\mathcal O(1)$ 是因为单旋仅在 $fa_x$ 为根时出现,最多一次。而单旋 Splay 的复杂度中前面一项是 $\Theta(m)$,这也是它假掉的原因。

由于 $\texttt{splay}$ 中 $\texttt{rotate}$ 后 $x$ 会代替 $fa_x$,换言之有 $siz^\prime(x_i)=siz(x_{i-1})$。那么总复杂度等于:$$ \mathcal O(1)+\sum\limits_{i=2}^m (\phi(x_{i-1})-\phi(x_i)) $$ 消掉其中大多数项,答案变为:$$ \mathcal O(1)+\phi(x_1)-\phi(x_m)\le \mathcal O(1)+\phi(x_1) $$ 由于 $|x_1|=|root|=n$,因此总复杂度为 $\mathcal O(\log n)$。

Splay 的应用

如果将 Splay 作为一棵普通平衡树,它不仅常数大还难调,并不优秀。

实际上,与其它普通平衡树不同,Splay 允许自由旋转的特性使它可以支持一些区间上的操作。

区间翻转

这是 Splay 的标志性应用,一般来讲,带有区间翻转字样的题目都可以考虑 Splay。

这里是用 Splay 维护区间翻转问题的模板。

我们建一个 Splay,里面存的是位置,即 $[1,n]$ 中的每个坐标。

每次我们要对区间 $[l,r]$ 进行翻转操作时,我们先将 $l-1$ 旋到根,再将 $r+1$ 旋到根的右结点。这样树就变成了这样:

这样,当前根结点右儿子的左子树就是我们要操作的区间。

那么我们借用线段树 Lazy-Tag 的思想,当执行将一棵子树翻转时,给它打上一个 tag,然后访问到时像线段树那样下传

这里必须注意:不能用 val 的值来判断,需要用 siz 的值决定递归到哪个子树中

因此,我们实际询问的点是:$l,\ r+2$。这里由于我们要实现将一个点旋到根的右结点的功能,我们需要将 $\texttt{splay}$ 魔改一下:

void splay(int p,int t) { // t=0 or t=rt
    for( int f=a[p].fa ; f!=t ; f=a[p].fa ) {
        if(a[f].fa!=t) rotate( which(f)==which(p) ? f : p );
        rotate(p);
    }
    if(a[p].fa==0) rt=p;
}

此外,由于翻转区间两次相当于没有进行操作,我们可以采用异或的方式维护 tag

最后,我们中序遍历一遍 Splay 即可。

Code

Lazy-Tag 的综合使用

怎么早年的 NOI 全是这些莫名奇妙的题/px

先咕着。

Splay in Ynoi

如果把修改中要求的 $x$ 的倍数去掉,那就是一个经典问题。

但这里要求是 $x$ 的倍数,因此考虑继续沿用只除不乘的性质。注意到总的除法次数至多是 $\mathcal O(n\log a_i)$,于是考虑维护。

对每个整数 $x$,将它的倍数的下标都扔进一棵 Splay 里,每次要除时直接把对应的 Splay 中区间 $[l,r]$ 截出来暴力处理即可。

这样可以做到 $\mathcal O(n\log a_i\log n)$,但是这样常数极大且实现复杂。

可以用 vector + 并查集换掉 Splay 来优化代码。

Code