$\rm{0x01}$ 闲话 · $LCT$的用途以及具体思路
咳,其实在我最近只是浅浅地学了一部分的基础上,窝觉得$LCT$其实就是一个用来维护森林连通性的。
嗯……因为其独特的性质所以也可以顺便维护好多东西,什么链上的最大值啊,链上的权值和啊……都可以维护——或者说,LCT是更加全能的树剖。
但其实吧……$LCT$打板子是很简单的,但是真正理解却一点儿也不简单。因为本身$splay$就很麻烦了,况且$splay$之前一直用于维护数列。要知道,此处的$splay$可是作为辅助树,维护一整个森林,并且可以支持序列中几乎全部操作——这就大大增高了理解难度。举个例子,你曾经认为已经难以理解、或者说不可以做的、比较复杂的区间翻转$Luogu3391$,在$LCT$里面有十分全面的涉及,但是被精简到了只有两行是用来描述这个内容的。显而易见的是,$LCT$虽然常数十分的大,但代码十分的短,比一棵完整的平衡树短了不少(实测50+行),与$FFT$一样具有着华丽的可观赏性,但是隐藏在之后的思维难度同样不可小觑。
也就是说我们是不是学的太草率、太浮躁了呢?快餐式地学完$LCT$,网上的每一篇博客都包教包会。但是我今天要整理的,是对于$LCT$真正的理解。希望各位看到这篇拙作的人可以获得一些什么。
$\rm{0x02}$ 闲话 · 关于$\rm{splay}$
道理我都懂,要想动态拆删一些东西,辅助树的形态可以改变是先决条件。看上去平衡树好像是个不错的选择,但是,选哪个作为辅助树呢?后宫佳丽三千我该翻谁的牌子呢
历史的重任最后落到了$\rm{splay}$的身上。然后$\rm{splay}$他居然:
他甚至还:
……
好吧,由于某些rqy也不知道的原因,如果不用$\rm{splay}$的话,复杂度是均摊$\Theta(\rm{nlog^2n})$, 而用$\rm{splay}$就可以做到均摊$\Theta(\rm{nlogn})$ ……但事实上,splay确实有他独特的性质,比如旋转到根啊之类的,比起其他种类的平衡树而言,更加适合$LCT$
$\rm{0x03}$ $LCT$的思路和基础操作
一 主要思路
主要思路嘛……大概是基于实链剖分的操作。
朴素的树剖是重链剖分,大体上就是将整棵树的链划分为轻边和重链,运用巧妙的性质做到$log$级别。而遗憾的是$LCT$维护的是森林的连通性,所以只能采用实链剖分。
而实链剖分大体上就是把边分为虚边和实边。其中实边串联起一个联通块,同一组实边存在、且仅存在于一棵$\rm{splay}$中。$\rm{splay}$和$\rm{splay}$之间由虚边相连。
实链剖分的好处呢?在于实链剖分是一种动态剖分,他可以随意改变边的虚实属性。而显然,重链剖分由于有着足够的理论依据和逻辑推演,所以轻重链是难以更改,或者说,不可更改的。So,实链剖分为动态树的动态打下了基础。
那么接下来我们来看一个$LCT$是如何定义的:
1、首先,一棵$LCT$管控的是一对分散的点,点以几棵分散的$splay$的形式聚集。起初整棵$LCT$是没有任何联系的,各自为战,各自为根。我们接下来会看到的$access$、$makeroot$等操作,都是在自己的联通块儿内部进行的操作。换句话讲,$LCT$维护的是有根森林,即组成森林的每个联通块都有其唯一的根。
2、实边串联起一个联通块,同一组实边存在、且仅存在于一棵$\rm{splay}$中。$\rm{splay}$和$\rm{splay}$之间由虚边相连。只有实边是有效的,虚边可以被认为不存在。但是两种边都没有用到显式存储,都是通过splay中的$Son$数组和$Fa$数组访问的。但虚边和实边的存储有区别:
3、虚边是认父不认子,即如果$Fa[x]==y$,那么$y$不存$x$这个儿子,但是$x$存$y$这个父亲。这样做是为了可以$Access$——因为其实在$Access$的子函数$splay$里,发挥作用的实际上是$Fa$指针。
4、实边是完整的双向存储。
5、显然的是,$\rm{splay}$中维护的是一条从存储上到下按在原树中深度严格递增的路径,且中序遍历$\rm{splay}$得到的每个点的深度序列严格递增。换句话讲,一个$\rm{splay}$里面不会出现在原联通块儿(树)中深度相同的两个点。在一棵$\rm{splay}$中,键值就是原树中的深度。
6、如果$x$是它所在$splay$的最左边的点,那么它在原森林里的父亲是$x$所在$splay$的根的$fa$, 否则就是$x$在$splay$上的前驱.
二 基础操作
$emm$所谓基础操作大概就是每个用到$LCT$的题几乎都要用到的操作。我们把$n$以实边相连的儿子记作实儿子。而由于只考虑实边不考虑虚边是一坨森林,算上虚边之后就成为了一棵树,所以我们把这棵实虚相见的树的根记为$root$
这个操作有着很迷的性质,其时间复杂度是均摊$\log n$的。而这个操作的目的是$Access(n)$表示从$root$向$n$打通一条实链,并以$n$点为最深度最大的点、$root$为深度最小的点形成一棵$\rm{splay}$。
不难看出,这个操作其实就是把原来$splay$的割据给改变了。
我们思考,如果此时我们$Access$完点$n$之后,理论上来讲,$n$点应该不再有实儿子了——显然,如果有实儿子的话,$splay$中是应该包含这个实儿子的——而这就不符合$n$是$\rm{splay}$中深度最大的点的性质了。而因为在splay中,点是以深度为键值的,所以我们要每次砍掉$\rm{splay}$中的右儿子——即砍掉原来的实儿子,并把刚刚诞生的$\rm{splay}$连上。
1 | inline void Access(int x) { |
然后这就是$Access$了。
$make\text{_}root$先从$root$向$n$打通一条路径,然后$splay$上去,最后$reverse$一下。此处由于一开始$n$的深度最大,$splay$之后深度依旧最大,但此时$n$是$splay$的根,所以$reverse(n)$就相当于翻转了整条树上的链,那么翻转之后,$n$的深度就变成了最小,于是就是这个联通块儿的根节点了。
1 |
|
此处$splay$中由于要下放标记,需要保证树的形态是正确的,所以我们用一个$stack$存一下,顺序下放标记。
此处的$Merge(x, y)$的意义是,拉起$x,y$中间的链,形成一个$splay$。这里就直接$Mkroot$一遍,然后$Access$即可。让哪个点当根应该都可以,只不过多$splay$几次可以保证优(毒)秀(瘤)的复(大)杂(常)度(数)。
upd:此处$splay$还有深层次的意图,就是可以保证现在$x$和$y$是相邻的,这样在cut的时候就会很方便了。
1 | inline void Merge(int x, int y) { Rooten(x), Access(y), splay(y) ; } |
如果保证$Link$和$Cut$都是合法的操作的话,$Link$直接连,$Cut$直接删即可。
1 | inline void Link(int x, int y){ Rooten(x) ; T[x].F = y ;} |
此处$Link$必须先$Mkroot$一下,否则树链就断了。连的是虚边(因为连实边就会改变原来$splay$的割据);$Cut$必须先$split$一下,保证两个点之间在同一棵$splay$中,加之我们的$Merge$操作中,一开始把$x$给$mkroot$了,再把$y$点$splay$上去,直接导致了现在$x$应该是$y$的孩子——于是就很开心的,可以直接$cut$了。
但事实上,天不遂人意……有时候这条边并不存在,盲目删除的话会导致$GG$,盲目连边的话也会导致树的形态爆炸,所以我们要进行一波操作……
- 1、$New-Link$
1 | inline void Link(int x, int y){ Rooten(x) ; if(Find(y) != x) T[x].F = y ;} |
此处的意义在于,如果我们发现两个点在一个子树里面,连接它们就破坏了树的性质。$Find$就是无比普通的$Find$。。。。233
但要注意啊,$Find$找的是原树中的根,不是$splay$。由于原树中根的深度一定最小,所以应该是$splay$中最靠左的点……所以不断找左儿子。
多$BB$一句,这个地方一定注意啊!$Find$只改变了$splay$的形态,$mkroot$改变的是原树中的根
- 2、$New-Cut$
1 | inline void Cut(int x, int y){ |
此处首先我们要判一下这两个点是不是直接相连。是否直接相连……在一棵$splay$中的体现,要克服两个问题,第一是要判断是否连通,还是$Find$操作。
之后我们需要判断是否满足恰好相隔一条边——注意,首先因为代码中的$x$比$y$在原树位置靠上($Rooten$了$x$),在$splay$中靠左,那么如果$y$有左儿子的话,说明一定有$Depth(x) < Depth(y\text{的左儿子们}) < Depth(y)$,其中$Depth$表示原树深度。那么此时原树中$x$和$y$之间,一定隔着一些节点。考虑树的性质,两点之间有且仅有一条简单路径——所以当$T[y].Son[0]$不指向$Null$时,$x$和$y$之间没有一条边,不能直接$Cut$。
剩下的就很简单了,$T[y].F$应该是$x$,否则也不是直接相连。
呃……其实就一处而已。就是:
1 | inline bool check(int x){ return T[T[x].F].Son[0] == x || T[T[x].F].Son[1] == x ; } |
这个地方$splay$双旋判断祖父的时候,不再用$\rm{if(g\text{_}fa)}$,而是用$\rm{if(check(fa))}$。原因很简单,我们的虚边也是有指向父亲的指针的,但是连接两个不同的$splay$
剩下的……大概就没了吧……
于是——
$\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}$
1 |
|
$\rm{0x00}$ 后记和参考
可写完了……嗝……打个肥宅嗝犒劳犒劳自己
怎么说呢,自从我开始学$LCT$到我写完这篇$blog$为止,是我十分难熬的时间,总时长接近一周。一开始看别人写的$LCT$,想当然地、草率地理解了理解,就开始打板子,对$LCT$一直是极为肤浅的认识。直到开始写,才发现自己哪个地方都不会,理解的半生不熟,总之很惨……
写博客真是一个陶冶情操的过程啊……包括做表情包
加油吧,$pks$!
$\rm{Reference}$
- $[1]$ :$Flash\text{_}Hu$的$blog$ $^{^{[\nearrow ]}}$
- $[2]$ :某篇论文,结合食用效果显著 $^{^{[\nearrow]}}$