Splay&LCT

· · 个人记录

\mathsf{Splay\& LCT}

\mathsf{Splay}

平衡树

Splay 规定：访问完一个节点之后要将其强制旋转到根节点，以此保持其均摊复杂度为 O(\log n)

核心操作为 rotate 和 Splay

rotate(x)

作用为将节点 x 向上旋转一层（代替其父亲的位置），分为左旋和右旋，由于结果是将儿子旋转到父亲位置，所以旋转方向也只和儿子是父亲的左儿子/右儿子有关

下图以右旋为例
代码

#define get(x) (ch[fa[x]][1]==x)//获取x是其父亲的左儿子还是右儿子
#define pushup(x) (sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+c[x])
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=get(x);
    if(ch[x][k^1]) fa[ch[x][k^1]]=y;
    ch[y][k]=ch[x][k^1];
    ch[x][k^1]=y;fa[y]=x;fa[x]=z;
    if(z) ch[z][ch[z][1]==y]=x;
    pushup(y);pushup(x);
    return ;
}

splay(x)

其作用为将节点 x 旋转到根位置（好像和一部分人的不一样）
分为双旋和单旋

双旋

如果自己和父亲成了一条方向一样的链

这时候需要先旋转父亲，这样在 x 的两个子树中会有一个子树的深度会比直接转 x 浅（换句话说，这样树会变得更平衡一些）
其他情况旋转自己 

void splay(int x)
{
    for(int y=0;y=fa[x],y;rotate(x))
    if(fa[y]) rotate(get(x)==get(y)?y:x);
    root=x;
    return ;
}

单旋

单旋就是只要 x 不是根就一直 rotate(x)
很好想也很好写但是单旋复杂度是假的

看图可以发现，用单旋每次都 splay 深度最深的节点在树的形态是一条链的时候对树不平衡的现状没有改观，每次 O(n)

但是现在洛谷的普通平衡树一题仍然可以使用单旋过掉（数据加强版没试qaq）

ins(x)

作用就是在 \mathsf{Splay} 中插入一个值为 x 的节点
按照 \mathsf{BST} 的性质在 \mathsf{Splay} 中从根往下走，如果遇到值相等的节点就让该节点的 c 加一，否则一定会走到一个空节点上，我们在遍历的过程中记录一下当前节点的父亲，然后新建节点，更新记录的父亲对应的儿子，然后把新加入的节点 splay 到根即可 

void ins(int x)
{
    int u=root,f=0;
    while(u)
    {
        if(val[u]==x) {++c[u],++sz[u],splay(u);return ;}
        f=u;u=ch[u][x>val[u]];
    }
    ++cnt;sz[cnt]=c[cnt]=1;val[cnt]=x;
    fa[cnt]=f;
    if(f) ch[f][x>val[f]]=cnt,pushup(f);
    splay(cnt);
    return ;
}

del(x)

作用是在 \mathsf{Splay} 中删除值为 x 的节点（如果有多个只删除一个）
按照 \mathsf{BST} 性质在 \mathsf{Splay} 中从根往下走，找到值为 x 的节点并将其 splay 到根（设这个节点为 u）
如果值为 x 的节点不止一个就直接让 u c 减一即可
否则，如果 u 的左右儿子中有空节点那么就直接让 u 被其中不为空的那个代替即可
否则，此时 u 有两个儿子，我们选择一个儿子代替 u ，然后把另外一个子树接到正确的地方即可

这里选择用 u 的右儿子代替自己，那么在 u 的右子树中找到最小的节点，让 u 的左儿子成为该节点的左儿子，然后将其 splay 到根

void del(int x)
{
    int u=root,v;
    while(u)
    {
        if(val[u]==x) {splay(u);break;}
        u=ch[u][x>val[u]];
    }
    if(c[u]>1) {--c[u],--sz[u];return ;}
    if(!ch[u][0]||!ch[u][1]) {root=ch[u][0]+ch[u][1],fa[root]=0;return ;}
    fa[ch[u][1]]=0;
    v=ch[u][1];u=ch[u][0];root=v;
    while(ch[v][0]) v=ch[v][0];
    fa[u]=v;ch[v][0]=u;
    pushup(u);pushup(v);
    splay(u);
    return ;
}

pre(x)/nxt(x)

这里可以先 ins(x)，此时 x 在根节点位置，那么其前驱即为根左子树中最大的节点（其后继即为根右子树中最小的节点），找到之后再 del(x) 即可

其他操作略
普通平衡树代码

\mathsf{LinkCutTree}

动态树，用来维护动态森林连通性
支持连边断边查询连通性查询路径信息等等

由于这时候的图是由若干棵树组成的，我们先讨论一棵树内的处理
对于一棵树，我们对这棵树进行树链剖分，不过不是常用的轻重链剖分，也不是长链剖分，而是虚实链剖分

什么是虚实链剖分？
虚实链剖分类似轻重链剖分，轻重链剖分是选择 sz 最大的儿子并将其与该儿子之间的连边定为重边，其他边定为轻边，若干条相连的重边组成一条重链；虚实链剖分则是由我们自己来定谁是虚边谁是实边

虚实链剖分怎么维护 \mathsf{LCT} 需要的东西？
类似轻重链剖分用线段树之类的数据结构维护链上信息，\mathsf{LCT} 使用 \mathsf{Splay} 维护链上的信息；轻重链剖分中一条重链上的点在线段树上对应的标号连续，而虚实链剖分中一条实链上的点组成一棵 \mathsf{Splay} ，我们称这些 \mathsf{Splay} 为辅助树，同时值得注意的是，实链是一条深度单调的链，而 \mathsf{Splay} 本身是一种 \mathsf{BST}，作为辅助树其关键字即为深度（即辅助树中一棵 \mathsf{Splay} 的中序遍历的节点深度是单调的），\mathsf{LCT} 就是利用这些 \mathsf{Splay} 维护信息来实现相关操作

可以发现，原树是由若干条实链之间用轻边连接起来构成的，而每一条实链在辅助树上对应一棵 \mathsf{Splay} 。

辅助树的轻重边存储

由这个方式，可以判断出原树中的边和辅助树中的边**一一对应** --- 辅助树有哪些操作？ （这些操作理解时经常弄错 "树根" 是指原图中的树根还是辅助树中的树根，我会尽量写清楚） #### 作为 $\mathsf{Splay}$ 最基础的 `splay(x)` 和 `rotate(x)` `splay(x)` 作用是将 $x$ 在辅助树中转到树根（让 $x$ 成为其所在的那一棵 $\mathsf{Splay}$ 的根节点），这个本来在 $\mathsf{Splay}$ 的时候就学过，但是因为 “认父不认子” 的存储方式导致 `splay` 要略略变动一下 ```cpp #define isroot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x) void splay(int x) { for(int y=0;y=fa[x],!isroot(x);rotate(x)) if(!isroot(y)) rotate(get(x)==get(y)?y:x); pushup(x); return ; } ``` 发现相对于仅仅作为平衡树的 `splay`，$\mathsf{LCT}$ 的 `splay` 不再以是否有父亲判断是否是根节点，因为由上面轻重边的存储我们知道，即使是一棵 $\mathsf{Splay}$ 的根也会有父亲，所以这里应该判断是否为自己所属的 $\mathsf{Splay}$ 的根（即连向父亲的边是不是实边） 同理 `rotate` 也有相应的变化，原来是对是否有父亲进行判断，现在不能直接这么判断，改动也很小： ```cpp void rotate(int x) { int y=fa[x],z=fa[y],k=get(x); if(!isroot(y)) ch[z][get(y)]=x; ch[y][k]=ch[x][k^1]; if(ch[x][k^1]) fa[ch[x][k^1]]=y; fa[y]=x;ch[x][k^1]=y;fa[x]=z; pushup(x);pushup(y); return ; } ``` #### `access` 非常重要的 `access(x)` 操作 `access(x)` 操作的作用是打通原图中的树根到节点 $x$ 的一条实链 实际上就是把原图根节点到点 $x$ 这条路径接起来，如果路径上的点原来还连有其他的实边那么全部断掉变虚 因为 $\mathsf{LCT}$ 信息的维护都挂在 $\mathsf{Splay}$ 上，`access(x)` 操作支持将原图根节点到 $x$ 节点的路径信息都集合到 $1$ 棵 $\mathsf{Splay}$ 中，此时访问这棵 $\mathsf{Splay}$ 的根节点就能得到一整个路径的信息，非常有用 ![](https://cdn.luogu.com.cn/upload/image_hosting/z2kj9f9z.png) 如图，执行 `access(x)` 结果如右 原树根节点 $\rightarrow x$ 这一条路径用实边连接起来，并且断掉原有的实边以保证实链是深度单调的 代码上： ```cpp void access(int x) { for(int p=0;x;p=x,x=fa[x]) splay(x),ch[x][1]=p,pushup(x); return ; } ``` 逻辑就是，依次走过从 $x$ 到原树根节点路径上的实链，连接当前这一条实链（`x`）和上一条实链（`p`）（将二者之间的虚边变成实边）同时断掉 `x` 原有的实边 实现上，首先 `splay(x)` ，这样深度比 `x` 深的点就都在 `x` 右子树（$\mathsf{BST}$），因为 $x$ 下方应该连接上一条实链，而上一条实链深度一定比 `x` 大，所以深度比 `x` 深的节点就是上一条实链，原来在 `x` 这一条实链中的点就从 `x` 断开（认父不认子性质，所以 `ch[x][1]=p` 这一句同时完成了虚边变实和原实边变虚） 这样一直到原树根节点，原树根节点所在的实链对应 $\mathsf{Splay}$ 根节点是没有父亲的，不然表明原树根节点还有连向父亲的虚边，这和根节点定义冲突，所以循环条件是 `x!=0`，又由于每次都是 `splay(x)` 所以 $fa[x]-x$ 一定是虚边，走这条边就可以到达下一条实链，一直走到根节点完成 `access` #### `makeroot(x)` `makeroot` 操作作用是将原树中的根节点变成 `x` ```cpp void rev(int x) { std::swap(ch[x][0],ch[x][1]); tag[x]^=1; return ; } void makeroot(int x) { access(x);splay(x); return rev(x); } ``` `access(x)`+`splay(x)` 将 `x` 和原树根节点连接起来之后将 `x` 转到了这棵 $\mathsf{Splay}$ 的根节点，这时候 $ch[x][1]=0$，因为 根$\rightarrow x$ 这条实链深度最深的是 $x$ ，不会有更深的（更深的原本连在 $x$ 下面，`access` 的时候断掉了） 因为我们想让 $x$ 成为根，所以现在 $x$ 深度应该为 $0$ ，最小，所有其左子树的节点应该去右子树，所以将 $x$ 的两个子树翻转（翻转部分详见文艺平衡树），翻转是要打标记的，标记需要下推（注意只能上向下推），所以 `splay` 操作需要添加下推标记这一步 ```cpp void pushdown(int x) { if(!tag[x]) return ; if(ch[x][0]) rev(ch[x][0]); if(ch[x][1]) rev(ch[x][1]); tag[x]=0; return ; } void update(int x) { if(!isroot(x)) update(fa[x]);//模拟栈，由于splay是先知道下面的节点，所以用栈，从下往上节点入栈，从上往下下推标记 return pushdown(x); } void splay(int x) { update(x);//***** for(int y=0;y=fa[x],!isroot(x);rotate(x)) if(!isroot(y)) rotate(get(x)==get(y)?y:x); pushup(x); return ; } ``` #### `findroot(x)` `findroot(x)` 作用是找到 `x` 所在原树中的树根 这个很好实现，`access(x)` 让原树根节点和 `x` 连起来，然后 `splay(x)`，此时原树根节点就在最左边 ```cpp int findroot(int x) { access(x);splay(x); while(ch[x][0]) pushdown(x),x=ch[x][0]; splay(x);//<-这个splay(x) 操作是给之后的操作用的，不要掉了 return x; } ``` 用这个判断连通性是很好的，因为维护森林连通性的时候如果询问 $x,y$ 是否联通，我们可以 `makeroot(x)` 然后检查 `findroot(y)` 是否等于 `x` 即可 #### `link(x,y)` `link(x,y)` 作用是让原森林中 `x,y` 联通，如果 `x,y` 已经联通则不操作，否则在 `x,y` 间连接一条边 实现也很简单，先 `makeroot(x)` ，然后检查 `findroot(y)` 是否为 `x` ，如果是 `x` 说明二者联通，不用操作，否则 `fa[y]=x` （ `x` 被 `makeroot` 了，不能 `fa[x]=y`） #### `cut(x,y)` `cut(x,y)` 作用是让原森林中的边 $x-y$ 断开，如果不存在边 $x-y$ 则跳过 主要是判断边 $x-y$ 的存在 首先最低的标准就是 $x$ 和 $y$ 联通，所以 `makeroot(x)` 然后检查 `findroot(y)` 即可 然后利用一条实链对应的 $\mathsf{Splay}$ 的中序遍历是深度单调的，中序遍历序列相邻两点有直接连边 `findroot(y)==x` 之后 $x,y$ 就已经在一棵 $\mathsf{Splay}$ 里面了，所以考虑中序遍历 $y$ 后面要紧接着 $x$ ，这要求 $fa[y]=x$ 并且 $y$ 没有左子树，$x$ 被 `makeroot` 之后没有左子树，所以中序遍历输出的第一个节点就是 $x$ ，$fa[y]=x$ 保证输出 $x$ 之后立即来到了 $y$ ，如果 $y$ 有左子树那么在 $x$ 之后输出的就是 $y$ 左子树中的某个节点，此时 $x-y$ 不存在 判断 $x-y$ 存在之后直接双向断边即可 ```cpp void cut(int x,int y) { makeroot(x); if(findroot(y)!=x||fa[y]!=x||ch[y][0]) return ; fa[y]=0;ch[x][1]=0; pushup(x); return ; } ``` #### `split(x,y)` 作用是将 $x,y$ 之间的唯一路径提到一棵 $\mathsf{Splay}$ 内，很简单，`makeroot(x)` 然后 `access(y)`，`splay(y)` 之后访问平衡树的 `y` 节点就能得到路径 $x,y$ 相关信息 ```cpp void split(int x,int y) { makeroot(x);access(y); return splay(y); } ``` [洛谷板子的代码](https://www.luogu.com.cn/paste/ea5i1d28)