数据结构也开始复习(学新的,虽然在纪中那边自学过)了
代码量非常友ke好guan
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$)的辅助树”
Part2. Link-Cut Tree(LCT)
为了达到 $O(\log_2n)$ 的单次复杂度,LCT 以 Splay 为内部数据结构。其核心操作是 Access(u)
。
Part2/1. 实链剖分
类似于树链剖分中的“重链剖分”,实链剖分也是把树剖分成若干条 各点深度不同的链。链上的边是实边,不在链上的边是虚边。
也可以这样理解:每个节点有最多一个 优先儿子(类似于重链剖分的重儿子),该点到它的优先儿子的边为实边,到其他儿子的边为虚边。
比如这样就是实链剖分:
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]; inline int Direc(){return fa->ch[1]==this;} inline bool IfRoot(){return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);} inline void SetChild(LNODE *Pch,int dir){ 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]
”,即 认父不认子。
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(){ 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; 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(); 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(); }
|
Part2/5. Access(u)
操作
用函数 Access(u)
来实现将 u 到 原树的根 这条链全部变成实链,并且把 u 的儿子全部变成轻儿子。比如这样
Hint. 注意是原树
把 u 的儿子都设为轻儿子其实就是在 Splay 上把深度大于 u 的点与 u 的边改为虚边。所以我们先 Splay(u)
,然后 u 的右子树就是 Splay 里深度比 u 大的点,所以再把 u 的右儿子设为虚边即可(也就是 u->ch[1]=NIL
)。
接下来把 u的父亲 与它的优先儿子(如果有的话)之间的实边断开,重新设 u 为 u的父亲 的优先儿子;也就是把 u 的父节点(父节点与 u 就不在一条链上了)的右儿子改为 u。把 u 移到父节点,然后继续……
代码是这样实现的:
1 2 3 4 5 6 7 8 9
| void *Access(LNODE *x){ LNODE *y=NIL; while(x!=NIL){ Splay(x); x->SetChild(y,1); x->PushUp(); y=x;x=x->fa; } }
|
Part2/6. MakeRoot(u)
& Link(u,v)
& Cut(u,v)
即把 u 改为它所在树的根(不改变形态),在 u,v 之间连上边(需要保证 u,v 不在同一棵树中)和断开 (u,v) 之间的边(需要保证 u,v 之间原来有边)。
Hint. 这里换根、连边、断边是在原树上
我们先把 u 到它的根的路径打通 Access(u)
,然后就形成了一条 u 到根的链,可以知道 u 是该链中深度最大的点。然后再 Splay(u)
,因为该链中的其他点的深度都小于 u,所以 u 只有左儿子。这个时候,我们只要把这条链整个反转就可以把 u 改为链中深度最小的点,也就是整棵树的根了。
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); return y; }
|
Part3/2. 求 LCA
需要理解一下:先 Access(u)
,再 Access(v)
,最后 Splay(u)
,然后就会有两种情况。
-
当 LCA 不为 u(也就是 u 不是 v 的祖先)时, fa[u]
就是 LCA。
-
此时再 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; bool Brev; LNODE *ch[2],*fa; void PushUp(){ if(this==NIL) return; ch[0]->PushDown();ch[1]->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;} void NewNode(int id,int 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; 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){ 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,欢迎提问~