LCT 学习笔记 & 复杂度证明 & 例题

LEWISAK · 2026-07-17 19:36:02 · 算法·理论

更多柚子好的阅读体验。

这种复杂度不太好证的统一单开一个部分证（3 部分）。

• 前置知识：Splay

1 算法介绍

给定一颗有点权树，思考下面的问题：

• 修改点权。
• 查询路径异或和。

发现这是小学六年级就学过的经典树剖问题🧐，但如果加入以下操作就困难了：

• 动态加边、删边。（保证始终是一个森林、每次询问的路径存在）

发现树剖无法做这个问题的核心原因在于加删边之后重边会巨大改变难以维护。

于是就有了 LCT 算法——通过巧妙钦定实虚边（对应树剖的重轻边）保证算法复杂度。

这种方式被称为实链剖分，在 LCT 中我们使用 Splay 维护每条实链。（不能用其他平衡树的原因是复杂度保持 \log n 需要 Splay 的精妙势能分析）

2 具体实现

2.1 辅助树

辅助树就是维护实链的 Splay 通过某种方式连接形成的树，对于原森林中的每一颗树都对应一颗辅助树，辅助树的性质：

• 辅助树的每个实链都用一个 Splay 维护，并且 Splay 的中序遍历对应实链从浅到深的每个点。
• 连成树的方法如下：Splay 的根指向其维护原树实链链顶的父亲，但对于这个点我们不修改它的儿子信息来表示这是条虚边，也就是说虚边都 “认父不认子”。

盗几张 OI-wiki 的图，对于这颗原树：

其辅助树可能长这样：

2.2 节点信息

int tot;
struct{
    int son[2],fa,sum,val,lazy;
}tr[200200];
#define fa(x) tr[x].fa
#define lz(x) tr[x].lazy
#define sum(x) tr[x].sum
#define val(x) tr[x].val
#define ls(x) tr[x].son[0]
#define rs(x) tr[x].son[1]
#define son(x,y) tr[x].son[y]

tot 表示当前节点个数。

son[0] 表示左儿子，son[1] 表示右儿子。

fa 表示父亲节点。

sum 表示 Splay 上子树异或和。

val 表示该节点的权值。

lazy 表示区间翻转标记（等会要用）。

2.3 辅助函数

容易实现的小函数合集。

void nw(int v){//新建一个权值为 v 的节点
    tot++;
    val(tot)=sum(tot)=v;
}
int get(int x){//获取 x 是父亲的右儿子还是左儿子（1 代表右儿子）
    return rs(fa(x))==x;
}
bool isrt(int x){//获取 x 是否是当前 Splay 的根（通过认父不认子的性质判断）
    return ls(fa(x))!=x&&rs(fa(x))!=x;
}
void up(int x){//上传
    sum(x)=sum(ls(x))^sum(rs(x))^val(x);
}
void tag(int x){//翻转节点
    swap(ls(x),rs(x));
    lz(x)^=1;
}
void down(int x){//下放懒标记
    if(lz(x)){
        tag(ls(x));tag(rs(x));
        lz(x)=0;
    }
}
void update(int x){//将 x 到根的所有节点的懒标记下放，以便 splay 操作。
    if(!isrt(x)) update(fa(x));
    down(x);
}

2.4 Splay 继承操作

这部分全是和 Splay 完全一样的操作，不会的考虑重修 Splay。

void rotate(int x){
    int y=fa(x),z=fa(y),c=get(x);
    if(!isrt(y)) son(z,get(y))=x;//注意这里判根要用函数判
    fa(son(x,!c))=y;
    son(y,c)=son(x,!c);
    fa(y)=x;
    son(x,!c)=y;
    fa(x)=z;
    up(y),up(x);
}
void splay(int x){
    update(x);
    int f=fa(x);
    while(!isrt(x)){
        if(!isrt(f)){
            rotate(get(f)==get(x)?f:x);
        }
        rotate(x);
        f=fa(x);
    }
}

2.5 access

LCT 最核心操作。

该函数表示将 x 到根路径上所有边改为实边，并且将与这些边相邻的边改为虚边。

例如对于下树：

它的辅助树可能为：

例如我们执行 access(N)，我们希望原树变为：

考虑从下向上合并 Splay，考虑先将 N 旋到根，然后我们需要将 N 和实儿子连边改成虚边。

考虑其实儿子在哪，由于 Splay 中序遍历是从浅到深的，所以其实儿子应该就是其右儿子，所以我们将其右儿子改为空来表示这是虚边，于是辅助树会变为：

接下来我们继续向上，对于 N 的父亲 I，我们仍然先进行 splay，对于已有的右儿子我们要将其改为虚边，接着要连实边，让右儿子变为 N，实际上就是将右儿子改为 N 即可。

也就是一直 splay 后改右儿子到根即可。

void access(int x){
    int y=0;
    while(x){
        splay(x);
        rs(x)=y;
        up(x);
        y=x;
        x=fa(x);
    }
}

2.6 makeroot

维护路径信息时 u,v 可能不在一个 Splay 中导致难以维护，考虑将 u 旋转到根后对 v access，我们现在就需要实现将某个点旋转到根的函数 makeroot。

这个函数实现也很简单，我们先 access(x)，我们翻转 x 到根的路径会改变 dfn 序，所以我们需要对整个 Splay 进行一次翻转， 也就是 splay(x) 后 tag(x)。

void makert(int x){
    access(x);
    splay(x);
    tag(x);
}

2.7 find

find(x) 用于找到 x 在原树上的根节点。

我们还是先 access(x),splay（x) 让 x 为根的 Splay 维护到 x 的根链信息，根据中序遍历为 dfn 序的性质，根应该就在 Splay 的最左下叶子处，所以不断跳左儿子即可。找到根后我们需要进行一次 splay 以保证复杂度。

int find(int x){
    access(x);
    splay(x);
    while(ls(x)){
        down(x);
        x=ls(x);
    }
    splay(x);
    return x;
}

2.8 link 与 cut

link(x,y) 的作用是在 x 和 y 之间连边。

此时我们先钦定 x 为 y 的虚儿子，只需要将 x 旋转到其原树上的根后将父亲设为 y 即可。

void link(int x,int y){
    makert(x);
    if(find(y)!=x) fa(x)=y;
}

cut(x,y) 的作用是删去 x 和 y 间的连边。

我们将 x 转到根后将 y 到根的链提出后 splay(x)，这样如果 x 到 y 间有连边那么 y 一定是 x 的实儿子。

void cut(int x,int y){
    makert(x);
    access(y);
    splay(x);
    if(fa(y)==x&&!ls(y)) fa(y)=rs(x)=0;
    up(x);
}

2.9 split

split(x,y) 的作用是将 x,y 间的路径单独提成一颗 Splay。

我们只需要让 x 变为原树上的根后提取 y 到根上的路径即可。

void split(int x,int y){
    makert(x);
    access(y);
    splay(y);
}

3 复杂度证明

LCT 中大部分操作的复杂度都基于 Access，故我们这里着重分析 Access 的复杂度（下文混淆树节点个数和 Access 调用次数）

1. splay 操作

   用和原版 Splay 一模一样的势能分析可以证明复杂度为均摊 O(\log n)。

2. 虚边访问

   将父亲 u 连向儿子 v 的虚边中 siz_v>\frac{1}{2}siz_u 的称为重虚边，其余称为轻虚边。

   设计势能函数 \phi 为所有重虚边的数量，均摊成本为实际操作成本加 \phi 变化量。

   • 经过重虚边：由于我们将其转化为实边，导致 \phi 减少，实际操作成本为 O(1)，所以经过重虚边不会对均摊成本产生影响。
   • 经过轻虚边：经典的是，每次经过轻虚边都会使 siz 至少翻倍，所以最多只有 O(\log_n) 条轻虚边。

   于是虚边访问的均摊成本为 O(\log_n)

综上，Access 的均摊复杂度为 O(\log_n)。

4 例题

[Codechef MARCH14] GERALD07加强版

题目大意