学习笔记 - LCT

数据结构也开始复习(学新的,虽然在纪中那边自学过)了

代码量非常keguan


Part1. 动态树问题

要求动态维护一个森林,支持删边加边(保证加边后仍是森林,即不会出现环),以及修改点权等操作。

对于森林的形态,支持以下:

  • Link(u,v):在 u,v 两点间连边 (u,v);
  • Cut(u,v):断掉边 (u,v);
  • FindRoot(u):找到 u 现在所在的树的根;

对于点权值,支持:

  • 修改/询问一条路径上的值;
  • 修改/询问一棵子树中的值;

现在已经出现的实现动态树问题的算法,公认单次操作的时间复杂度为 $O(\log_2n)$ 。其中 Link-Cut Tree(LCT) 是一种比较简单的解决动态树问题的数据结构。

实际上,现有的解决动态树问题的方法都是 “把原树等价对应到一棵深度平均($\log_2n$)的辅助树


为了达到 $O(\log_2n)$ 的单次复杂度,LCT 以 Splay 为内部数据结构。其核心操作是 Access(u)

Part2/1. 实链剖分

类似于树链剖分中的“重链剖分”,实链剖分也是把树剖分成若干条 各点深度不同的链。链上的边是实边,不在链上的边是虚边。

也可以这样理解:每个节点有最多一个 优先儿子(类似于重链剖分的重儿子),该点到它的优先儿子的边为实边,到其他儿子的边为虚边。

比如这样就是实链剖分:

png1

Part2/2. Splay 的节点结构体

Hint. 下面的一些函数是定义在一个结构体中的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct LNODE *NIL;
struct LNODE{
int Vsiz,Brev;
LNODE *fa,*ch[2];
//判断 u 是父亲的左儿子还是右儿子
inline int Direc(){return fa->ch[1]==this;}
//判断 u 是否是当前 Splay 的根
inline bool IfRoot(){return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);}
inline void SetChild(LNODE *Pch,int dir){ //修改 u 的儿子为 Pch,dir=0为左儿子,dir=1为右儿子
ch[dir]=Pch;
if(Pch!=NIL) Pch->fa=this;
}
inline void PushUp(){
if(this==NIL) return;
Vsiz=ch[0]->Vsiz+ch[1]->Vsiz+1;
}
//下传反转标记
inline void PushDown(){
if(!Brev) return;
if(ch[0]!=NIL) ch[0]->Brev^=1;
if(ch[1]!=NIL) ch[1]->Brev^=1;
swap(ch[0],ch[1]);
Brev=0;
}
};

Part2/3. Splay

LCT 的辅助树(还记得什么是辅助树吗)是由多棵 Splay 维护的,其中每棵 Splay 维护的是树上的一条实链,每个点的权值为点的深度。所以可以得到,在同一棵 Splay 中,“左儿子的深度<根的深度<右儿子的深度”(而且每条实链上的点深度都不同,所以 Splay 里的每个点深度都不同)。

  • 如果边 (u,v) 是实边,在辅助树上体现为 u,v 在同一棵 Splay 中;
  • 如果边 (u,v) 是虚边,在辅助树上体现为 “u所在的实链的最高点top[u]的父亲指针指向v,但是v的孩子指针没有指向top[u]”,即 认父不认子

png2

Part2/4. Rotate(u) & Splay(u)

虽然 Splay 是 LCT 的内部结构,但是实际实现时对 Splay 有所修改。由于 LCT 并不需要知道每棵 Splay 的根具体是谁,只需要知道某个点是不是 Splay 的根就行了。

判断一个点 u 是否是该 Splay 的根其实比较简单:① u 的父亲是 null (非常显然);② u 到 u的父亲 的边是虚边,只要判断在 Splay 中 u的父亲 是否存在一个儿子为 u。

1
2
3
inline bool IfRoot(){ //this 指向 节点u
return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);
}

首先 Splay(u) 操作只会在 u 所在的 Splay 中操作,也就是只会在 u 所在的实链上操作。所以对应的,Rotate(u),Splay(u) 有几处修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Rotate(LNODE *x){
LNODE *y=x->fa;
y->PushDown();x->PushDown();
int dir=x->Direc();
if(y->IfRoot()) x->fa=y->fa; //如果 y 是当前 Splay 的根节点,只能连虚边
else y->fa->SetChild(x,y->Direc());
y->SetChild(x->ch[!dir],dir);
x->SetChild(y,!dir);
y->PushUp();
}
void Splay(LNODE *x){
stack<LNODE*> stk;
while(!x->IfRoot()) stk.push(x);
x->PushDown();
while(!stk.empty()) stk.top()->PushDown(),stk.pop();
//Splay 的 PushDown 必须要从上到下 PushDown
while(!x->IfRoot()){ //这里判断当前 Splay 的根
LNODE *y=x->fa;
if(y->IfRoot()) Rotate(x); //同上
else{
if(x->Direc()==y->Direc()) Rotate(y);
else Rotate(x);
Rotate(x);
}
}
x->PushUp();
}

Part2/5. Access(u)操作

用函数 Access(u) 来实现将 u 到 原树的根 这条链全部变成实链,并且把 u 的儿子全部变成轻儿子。比如这样

png3

Hint. 注意是原树

把 u 的儿子都设为轻儿子其实就是在 Splay 上把深度大于 u 的点与 u 的边改为虚边。所以我们先 Splay(u),然后 u 的右子树就是 Splay 里深度比 u 大的点,所以再把 u 的右儿子设为虚边即可(也就是 u->ch[1]=NIL)。

接下来把 u的父亲 与它的优先儿子(如果有的话)之间的实边断开,重新设 u 为 u的父亲 的优先儿子;也就是把 u 的父节点(父节点与 u 就不在一条链上了)的右儿子改为 u。把 u 移到父节点,然后继续……

png4

代码是这样实现的:

1
2
3
4
5
6
7
8
9
void *Access(LNODE *x){
LNODE *y=NIL; //用来保存上一个 x
while(x!=NIL){
Splay(x); //先转到 Splay 的根
x->SetChild(y,1); //断开原来与优先儿子的实边,并将右儿子的边设为实边
x->PushUp();
y=x;x=x->fa; //上移一层处理
}
}

即把 u 改为它所在树的根(不改变形态),在 u,v 之间连上边(需要保证 u,v 不在同一棵树中)和断开 (u,v) 之间的边(需要保证 u,v 之间原来有边)。

Hint. 这里换根、连边、断边是在原树上

我们先把 u 到它的根的路径打通 Access(u),然后就形成了一条 u 到根的链,可以知道 u 是该链中深度最大的点。然后再 Splay(u),因为该链中的其他点的深度都小于 u,所以 u 只有左儿子。这个时候,我们只要把这条链整个反转就可以把 u 改为链中深度最小的点,也就是整棵树的根了。

png5

1
2
3
4
void MakeRoot(LNODE *x){
Access(x);Splay(x);
x->Brev=true; //反转标记(懒标记)
}

有了 MakeRoot()Link(u,v) 就简单多了。只要把 x 改为当前树的根,然后把 x 接到 y 的下面、作为 y 的子树就可以了。

1
2
3
4
void Link(LNODE *x,LNODE *y){
MakeRoot(x);
x->fa=y;
}

另外 Cut(u,v) 也比较好理解:先把 u 改为当前树的根,就可以通过 Access(v) 来打通 u 到 v 的路径,然后 Splay(v) 就可以使 u,v 相邻,而且 u 是 v 的左儿子。此时只要断开 u,v 之间的边。

1
2
3
4
5
6
void Cut(LNODE *x,LNODE *y){
MakeRoot(x);
Access(y);Splay(y);
y->ch[0]=NIL;y->PushUp();
x->fa=NIL;
}

Part3. LCT 的其他操作

Part3/1. 连通任意两点的路径

只要是无根树,我们就可以随意 MakeRoot();所以只要把路径一端 u 改为树的根,就可以通过 Access(v) 打通 u 到 v 的路径了。

1
2
3
4
5
LNODE *Road(LNODE *x,LNODE *y){
MakeRoot(x);
Access(y);Splay(y); //Splay 过后 y 就存储了整个 Splay 也就是从u到v的路径的信息了
return y;
}

Part3/2. 求 LCA

需要理解一下:先 Access(u),再 Access(v),最后 Splay(u),然后就会有两种情况。

  1. png6

    当 LCA 不为 u(也就是 u 不是 v 的祖先)时, fa[u] 就是 LCA。

  2. png7

    此时再 Splay(u)fa[u] 就为空,此时可以判断出 u 本身就是 LCA。

1
2
3
4
5
6
7
LNODE *LCA(LNODE *x,LNODE *y){
Access(x);
Access(y);
Splay(x);
if(x->fa==NIL) return x;
else return x->fa;
}

Part4. LCT版子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
struct LNODE *NIL; //可以这样在定义结构体之前声明结构体变量
struct LNODE{
int Vsiz,Vsum,Vval; //这里就维护链上的权值和
//Vsiz:Splay中该子树的大小;Vsum:Splay中该子树的元素和;Vval:该点的权值
bool Brev; //反转标记
LNODE *ch[2],*fa;
void PushUp(){
if(this==NIL) return;
ch[0]->PushDown();ch[1]->PushDown(); //我的写法中只有PushDown过后该节点才会是真实值
Vsiz=ch[0]->Vsiz+ch[1]->Vsiz+1;
Vsum=ch[0]->Vsum+ch[1]->Vsum+Vval;
}
void PushDown(){
if(Brev){
Brev=false;
swap(ch[0],ch[1]);
if(ch[0]!=NIL) ch[0]->Brev^=1;
if(ch[1]!=NIL) ch[1]->Brev^=1;
}
}
bool IfRoot(){return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);}
bool Direc(){return fa->ch[1]==this;}
void SetChild(LNODE *Pch,int dir){
ch[dir]=Pch;
if(Pch!=NIL) Pch->fa=this;
}
};
struct LCT{
LNODE Lpol[N+3]; //内存池
void Init(){ //初始化
NIL=Lpol;
NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;
NIL->Vsiz=NIL->Vsum=NIL->Vval=0;
}
LNODE *Ind(int id){return Lpol+id;} //取得 Lpol[id] 的指针
void NewNode(int id,int Vv){ //将编号为 id 的点初始化点权为 Vv
LNODE *p=Ind(id);
p->Vsum=p->Vval=Vv;
p->Vsiz=1;
p->ch[0]=p->ch[1]=p->fa=NIL;
}
void Rotate(LNODE *x){
LNODE *y=x->fa;
int dir=x->Direc();
if(y->IfRoot()) x->fa=y->fa;
else y->fa->SetChild(x,y->Direc());
y->SetChild(x->ch[!dir],dir);
x->SetChild(y,!dir);
y->PushUp();
}
void Splay(LNODE *x){
stack<LNODE*> stk; //一定要从上到下 PushDown
for(LNODE *y=x;;y=y->fa){
stk.push(y);
if(y->IfRoot()) break;
}
while(!stk.empty()){
stk.top()->PushDown();
stk.pop();
}
while(!x->IfRoot()){
LNODE *y=x->fa;
if(y->IfRoot()) Rotate(x);
else{
if(x->Direc()==y->Direc()) Rotate(y);
else Rotate(x);
Rotate(x);
}
}
x->PushUp();
}
void Access(LNODE *x){
LNODE *y=NIL;
while(x!=NIL){
Splay(x);
x->SetChild(y,1);
x->PushUp();
y=x;x=x->fa;
}
}
void MakeRoot(LNODE *x){
Access(x);Splay(x);
x->Brev^=1;
}
LNODE *FindRoot(LNODE *x){
Access(x);Splay(x);
while(x->ch[0]!=NIL) x=x->ch[0];
Splay(x);
return x;
}
void Link(LNODE *x,LNODE *y){
MakeRoot(x);
x->fa=y;
}
void Cut(LNODE *x,LNODE *y){
MakeRoot(x);
Access(y);Splay(y);
y->ch[0]=NIL;y->PushUp();
x->fa=NIL;
}
LNODE *Road(LNODE *x,LNODE *y){
MakeRoot(x);
Access(y);Splay(y);
return y;
}
LNODE *LCA(LNODE *x,LNODE *y){ //注意 MakeRoot 过后 LCA 可能会变
Access(x);
Access(y);
Splay(x);
if(x->fa==NIL) return x;
else return y;
}
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问~

0%