LCT学习笔记
LCT学习笔记
先导
老师：给你一棵树，要求维护其中任意两点间的某种操作。
小A：老师我会！这题用树链剖分！
老师：如果还需要考虑两个树之间连边呢？
小A：老师我也会！把编号连续一下，设定为轻儿子用平衡树做动态树剖就行。
老师：如果需要考虑连边、断边、两点间操作？
小A：老师动态树剖也能做！
小B：老师这个可以用 LCT 做！
（以上对话充分体现了 LCT 的可替代性）。
性质
总之今天的学习内容就是 LCT。如上面的问题所说，其实 LCT 就相当于支持断边和连边的动态树剖，可以做到所有树剖可以做到的操作，事不宜迟，快来学习吧。
LCT 其实相当于一个森林，维护着若干棵 Splay 树（我认为用 Splay 的原因是创造者不会/更喜欢 Splay是可以很方便的利用 splay 操作把节点放到顶端，同时很方便的使复杂度正确）。它有一套建树的规则，是这样的：
-
每一个 Splay 维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历 Splay 得到的每个点的深度序列严格递增。
-
每个节点包含且仅包含于一个 Splay 中。
-
边分为实边和虚边，实边包含在 Splay 中，而虚边总是由一棵 Splay 指向另一个节点（指向该 Splay 中中序遍历最靠前的点在原树中的父亲）。
-
因为性质 2，当某点在原树中有多个儿子时，只能向其中一个儿子拉一条实链（只认一个儿子），而其它儿子是不能在这个 Splay 中的。那么为了保持树的形状，我们要让到其它儿子的边变为虚边，由对应儿子所属的 Splay 的根节点的父亲指向该点，而从该点并不能直接访问该儿子（认父不认子）。
各种操作
先说几个基本操作，具体解释看注释。
bool nroot(int x){//是否不是root
return ls(f[x])==x||rs(f[x])==x;//如果x的父亲的左右子树儿子都不是x，那x就是根节点，否则不是
}
void pushup(int x){//更新值 因为需要维护异或和 具体参考文艺平衡树
s[x]=s[lc]^s[rc]^v[x];//x位置的答案是左右子树的答案异或上x位置的值
return;
}
void pushr(int x){//打翻转标记 具体参考文艺平衡树
swap(lc,rc);//交换左右子树
r[x]^=1;//打翻转标记
return;
}
void pushdown(int x){//下放翻转标记 具体参考文艺平衡树
if (r[x]){//如果有翻转标记
if (lc) pushr(lc);//下放到左子树
if (rc) pushr(rc);//下放到右子树
r[x]=0;//清空标记
}
return;
}因为 LCT 需要 Splay 树，所以我们先来看 Splay 树的操作，这里面就涉及两个操作——“Splay” 和 “Rotate”。
rotate操作
旋转有左旋或者右旋两者，旋转的效果就是让目标节点向上走一层，我们以右旋为例子进行介绍。
假设我们的目标节点是 2 号节点，要从一图转到二图，我们发现旋转的过程大概是这样的：
- 把 2 号节点和 1 号节点分离开。
- 1 号节点缺少左子树，于是用二号节点的右子树补上。
- 2 号节点缺少右子树，于是用一号节点补上。
然后我们可以发现，我们并没有必要真的把两棵树分开，我们直接改变即可。对于左旋，由于是右旋的反向操作，所以只要把所有的涉及 x 左右儿子的操作都反向过来就行。于是实现就是这样子的：
void rot(int x){
int y=f[x],z=f[y],k=rs(y)==x,w=c[x][!k];//x的父亲 x父亲的父亲 x是它父亲的左儿子还是右儿子 x的异侧节点
if (nroot(y)) c[z][y==rs(z)]=x; //如果y还有父亲，那么就把y父亲的y位置儿子替换为x
c[x][!k]=y;//把y的异侧儿子换成y
c[y][k]=w;//把y空出来的子树换成x在那个位置的子树
if (w) f[w]=y;//如果x在那个位置有子树，就令它的父亲为y
f[y]=x;//把y的父亲定为x
f[x]=z;//令x的父亲为y原先的父亲
pushup(y);//更新y
return;
}splay操作
这个操作是为了让 x 变成此 splay 树的根节点而做的。
考虑两种情况，即 x 对于 x 的父亲和 x 的父亲对 x 的父亲的父亲同侧和异侧。
同侧：
其实很明显就可以发现，其实我们只要把 x 以同一种方向向上走两步即可。
异侧：
这里需要先让x的父亲做一种旋转，然后让x做另一种旋转即可（此步骤不能改变，因为如果改变，则新树不满足原树性质（大小关系））。
因为我们的旋转是自适应的，所以我们就可以简化为这样一句口诀：
同侧转 xx，异侧转父 x。
体现到代码里是这样的：
void splay(int x){
int y=x,z=0;//先把x以上的翻转标记下放，防止标记混乱
st[++z]=y;//把x放入栈
while (nroot(y)) st[++z]=y=f[y];//不断放入栈，直到根节点
while (z) pushdown(st[z--]);//逐个下放标记
while (nroot(x)){//如果x没有被放到根节点就继续做
y=f[x],z=f[y];//x的父亲 f父亲的父亲
if (nroot(y)) rot((x==ls(y))^(y==ls(z))?x:y);//如果y不是根节点，就考虑x、y是否同侧，然后进行第一步旋转
rot(x);//第二步固定旋转x
}
pushup(x);//更新x
return;
}接下来就到了 LCT 特有的操作。
核心操作——access
其目的是把根节点到目标节点的路径放在同一个 splay中。
这是原树的一个剖分：
这是一个可能的 LCT：
如果我们要 access(N)，那么我们其实要得到这样一个效果：
我们看最初包含 N 的这个 LCT，因为 splay 树进行 splay 后保证原树的大小关系，所以我们可以把 splay(N) ，那么 N 的右子树就是在原树上深度大于 N 的，这些应该被舍弃；而N的左子树是深度小于 N 的节点，应该保留。最后进行一次 pushup ，如下图：
然后我们进入 N 现在的父亲节点，重复这样的操作，但是值得注意的是，我们需要把新 splay 树的右子树定为前一次建出来的 splay，来达到我们最后想达到的效果，显然的，如果因为我们第一次做这个操作的前一次操作的根节点为 0（数组初始值），所以我们可以直接把整个 access 同一成以下操作：
- splay(当前节点)。
- 当前节点的右子树=前一次计算出的树。
- update(当前节点)。
对于上面那棵树剩下的几步操作是这样的：
1.
2.
3.
代码为：
void access(int x){
for (int y=0;x;x=f[y=x]){//设定第一次的前一次为0，每次把x作为当前节点，y作为上一次的根节点
splay(x);//splay(x)
rc=y;//把x的右子树设为y
pushup(x);//pushup(x)
}
return;
}另一个较为核心的操作——makeroot
这个操作的目的是让一个节点成为原树的父亲。
我们先把根节点到目标节点放在一个树里，即 access(目标节点)。
然后我们会发现这个树上的所有节点都应该比目标节点的深度小，我们 splay(目标节点) 之后，所有的节点就都被统一到目标节点的左子树上去。我们可以发现，如果我们把整棵 splay 进行翻转，那所有的右子树都变成了左子树，也就是本应该比另外一者深度大的节点变小了，因此目标节点也变成了根节点。
总结下来，共有三步：
- access(目标节点)。
- splay(目标节点)。
- pushr(目标节点)。
代码如下：
void makeroot(int x){
access(x);splay(x);//打通x和根节点 使splay变成链
pushr(x);//翻转splay
return;
}findroot操作
这个操作是寻找目标节点所在树的根节点的。
很好理解，将其和根节点打通并连成链之后，把它 splay 上去，然后一直向左找原树深度最小的节点即可。代码如下：
int findroot(int x){//找到x所在原树的根
access(x);splay(x);//打通x和根节点 把x放到根上去
while(lc) pushdown(x),x=lc;//一直向左子树走，直到无法再走，这个位置就是左子树
splay(x);//因为一些复杂度原因，这里需要把根splay上去
return x;//返回结果
}split操作
这个操作是把两个节点之间的路径提出来成为一个 splay。
很好想，我们只要把一个节点变成根节点，另一个节点和根节点打通即可，代码如下：
void split(int x,int y){//要把x到y提出来
makeroot(x);//让x成为根节点
access(y);//打通x到y
splay(y);//为了方便操作，我们令y成为新树的根节点
return;
}link操作
这个操作是为了在两个点之间加条边。
直接把一个节点变成它所在树的根节点，然后如果另一个节点和它不在同一个树上，那么直接把第一个节点所在树挂在第二个节点上即可，因为 LCT 认父不认子的特性，这样显然是对的，代码如下：
void link(int x,int y){//在x和y之间加一条边
makeroot(x);//让x成为它所在树的根
if (findroot(y)!=x) f[x]=y;//如果两者不在同一棵树上，那就把x所在树连在y下面
return;
}cut操作
此操作是为了把两个节点之间的边断开。
我们需要考虑这条边不存在的情况，我们先把目标节点 1 变成所在树的根，然后我们发现，因为两目标节点之间存在边，所以深度差最多为 1，同时因为次数目标节点 1 为原树的根，所以目标节点二一定在目标节点 1 的右子树上，并且不存在左子树。总结下来，可以断边需要满足以下条件（让目标节点 1 作为根节点之后）：
- 两目标节点在同一子树。
- 目标节点 2 的父亲为目标节点 1。
- 目标节点 2 无左子树。
然后接下来我们之间把目标节点 1 的右儿子和目标节点 2 的父亲清空即可，因为目标节点 1 少了一个儿子，所以需要做一次 pushup，代码如下：
void cut(int x,int y){//断开x到y的边
makeroot(x);//让x成为x所在原树的根节点
if (findroot(y)==x&&f[y]==x&&!ls(y)){//如果x和y在同一个子树中 并且 y的父节点是x 并且 y没有左子树
rc=f[y]=0;//清空x的右儿子和y的父亲
pushup(x);//更新x
}
return;
}这就是所有常用的 LCT 操作，也是 LCT 模板里面的所有操作，这里给出模板的代码：
#include <bits/stdc++.h>
using namespace std;
namespace MySpace{
#define lowbit(x) (x&(-x))
#define sqrt __builtin_sqrtf //使用硬件加速的开方
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
#define whileu(p) while (p--)
#define forl(a,b,c) for (auto a=b;a<=c;a=a+1)
inline void read() {}
template <typename T, typename... R>
inline void read(T &x,R &... oth){
x=0;T f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
x*=f;
read(oth...);
return;
}
template<typename T>
T qpow(T a,T n,T p){
T res=1;
while (n){
if (n&1) res=1ll*res*a%p;
a=1ll*a*a%p;
n>>=1;
}
return res;
}
template<typename T>
T gcd(T a,T b){return (b>0?gcd(b,a%b):a);}
template<typename T>
T exgcd(T a,T b,T& x,T& y){
if (b<=0ll){
x=1ll,y=0ll;
return a;
}
T t=x;
T d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
template<typename T>
T inv(T a,T p){
if (a==1) return 1ll;
T x,y;
if (exgcd(a,p,x,y)!=1ll) return -1ll;
else return (x+p)%p;
}
}
using namespace MySpace;
//const int INF=0x66CCFF66;
#define ls(x) c[x][0]//x的左儿子
#define rs(x) c[x][1]//x的右儿子
#define lc c[x][0]//x的左儿子
#define rc c[x][1]//x的右儿子
const int maxn=3e5+5;
int f[maxn];//父亲
int c[maxn][2],v[maxn];//左右儿子 节点上带的值
int s[maxn],st[maxn];//节点上带的答案 手写栈
bool r[maxn];//翻转标记
int n,m;
int opt,x,y;
bool nroot(int x){//是否不是root
return ls(f[x])==x||rs(f[x])==x;//如果x的父亲的左右子树儿子都不是x，那x就是根节点，否则不是
}
void pushup(int x){//更新值 因为需要维护异或和 具体参考文艺平衡树
s[x]=s[lc]^s[rc]^v[x];//x位置的答案是左右子树的答案异或上x位置的值
return;
}
void pushr(int x){//打翻转标记 具体参考文艺平衡树
swap(lc,rc);//交换左右子树
r[x]^=1;//打翻转标记
return;
}
void pushdown(int x){//下放翻转标记 具体参考文艺平衡树
if (r[x]){//如果有翻转标记
if (lc) pushr(lc);//下放到左子树
if (rc) pushr(rc);//下放到右子树
r[x]=0;//清空标记
}
return;
}
void rot(int x){
int y=f[x],z=f[y],k=rs(y)==x,w=c[x][!k];//x的父亲 x父亲的父亲 x是它父亲的左儿子还是右儿子 x的异侧节点
if (nroot(y)) c[z][y==rs(z)]=x; //如果y还有父亲，那么就把y父亲的y位置儿子替换为x
c[x][!k]=y;//把y的异侧儿子换成y
c[y][k]=w;//把y空出来的子树换成x在那个位置的子树
if (w) f[w]=y;//如果x在那个位置有子树，就令它的父亲为y
f[y]=x;//把y的父亲定为x
f[x]=z;//令x的父亲为y原先的父亲
pushup(y);//更新y
return;
}
void splay(int x){
int y=x,z=0;//先把x以上的翻转标记下放，防止标记混乱
st[++z]=y;//把x放入栈
while (nroot(y)) st[++z]=y=f[y];//不断放入栈，直到根节点
while (z) pushdown(st[z--]);//逐个下放标记
while (nroot(x)){//如果x没有被放到根节点就继续做
y=f[x],z=f[y];//x的父亲 f父亲的父亲
if (nroot(y)) rot((x==ls(y))^(y==ls(z))?x:y);//如果y不是根节点，就考虑x、y是否同侧，然后进行第一步旋转
rot(x);//第二步固定旋转x
}
pushup(x);//更新x
return;
}
void access(int x){//打通x和根节点
for (int y=0;x;x=f[y=x]){//设定第一次的前一次为0，每次把x作为当前节点，y作为上一次的根节点
splay(x);//splay(x)
rc=y;//把x的右子树设为y
pushup(x);//pushup(x)
}
return;
}
void makeroot(int x){//把x改为原树的根
access(x);splay(x);//打通x和根节点 使splay变成链
pushr(x);//翻转splay
return;
}
int findroot(int x){//找到x所在原树的根
access(x);splay(x);//打通x和根节点 把x放到根上去
while(lc) pushdown(x),x=lc;//一直向左子树走，直到无法再走，这个位置就是左子树
splay(x);//因为一些复杂度原因，这里需要把根splay上去
return x;//返回结果
}
void split(int x,int y){//要把x到y提出来
makeroot(x);//让x成为根节点
access(y);//打通x到y
splay(y);//为了方便操作，我们令y成为新树的根节点
return;
}
void link(int x,int y){//在x和y之间加一条边
makeroot(x);//让x成为它所在树的根
if (findroot(y)!=x) f[x]=y;//如果两者不在同一棵树上，那就把x所在树连在y下面
return;
}
void cut(int x,int y){//断开x到y的边
makeroot(x);//让x成为x所在原树的根节点
if (findroot(y)==x&&f[y]==x&&!ls(y)){//如果x和y在同一个子树中 并且 y的父节点是x 并且 y没有左子树
rc=f[y]=0;//清空x的右儿子和y的父亲
pushup(x);//更新x
}
return;
}
signed main(){
read(n,m);
for (int i=1;i<=n;i++) read(v[i]);
while (m--){
read(opt,x,y);
if (opt==0) split(x,y),printf("%d\n",s[y]);//splay树根上记录的值就是整棵树的值
if (opt==1) link(x,y);
if (opt==2) cut(x,y);
if (opt==3) splay(x),v[x]=y;//要先把splay一下再改，不然标记会出问题
}
return 0;
}AC记录。
部分内容摘自这里。
（图源1） （图源2）。
另，有一个叫ETT（伪）的东西比这个好写，其思路为用平衡树维护原树的dfs序，同时维护原树的树上前缀和来维护链操作，比这个好写多了，并且支持fhqtreap。