6
26
2015
3

动态树拓展相关

前言

  本文主要介绍Top-Tree、Euler-Tour-Tree+LCT和一种奇怪的未命名的动态树


先扯两句

  本文到最后一部分之前是在NOI之前写的。

  现在离NOI结束大概有两三个星期了,期间一直没上过blog。

  当时确实挺不甘心的,现在想来也是实力不济,另外比我不走运的人还有太多太多。

  两年前sone爷rk54,hqw rk56,今年拿了个rk55大概是可以连起来了,挺棒的。

 

  前几天想起了这茬,想想也该在这里和OI道别一下。

  更完这篇文章以后,大概还会更一篇文章,不过和OI无关了,也就是说,这是我最后一次以OIer的身份写完这篇学术性文章。

  关于最后一部分那个东西,应sone爷的说法,我本来也想要写到集训队论文里去,现在看来是没这个机会了,那就和大家分享一下吧。

  有时候想想,如果我不研究这些在OI届不太有用的东西,多研究研究贪心脑洞啥的或许就有Au了?——已经无所谓了,像我这种人如果Au了大概会白白挥霍一年青春吧,上天也在为我好呢。

  就这样吧。

  希望大家能看完,如有错误欢迎指出。

                                                   ——by 已经退役的无脑洞选手Memphis


Top-Tree

简介

 这是什么?A:sb东西

  一种Link-Cut-Tree的拓展,以维护子树信息著称。

  【听说应该叫AAA树?不是很懂这一套理论,反正叫Toptree大家都知道是啥,就这么叫了吧>.<】

  【好像Tarjan论文还给加了个修饰“自适应”,你问我辛普森和自适应辛普森的区别是什么,我也不知道>.<】

引入

 我们该如何动态维护子树信息?先从一种动态树的解决方式——Link-Cut-Tree(LCT)的复杂度证明说起。

  首先大家应该都会LCT和树链剖分,不会的还请先不要看这篇文章。

  以下证明部分参考杨哲的集训队作业《QTREE解法的一些研究》

Link-Cut-Tree的复杂度分析

  我们知道LCT和树链剖分都有轻重链之分,然而LCT的轻重链是动态变化的,树剖却不是。

  我们先把一棵树树链剖分,定义轻边为不在重链上的边,重边为在重链上的边。再对LCT做定义,一个节点在重链【此处的重链为LCT的动态重链,和树剖无关】上的直接儿子定义为preferred child,连向该儿子的边定义为preferred edge。

  在LCT的access操作中,我们只要证明preferred child的更改次数是均摊[tex]O(n\log n)[/tex]的,就可以证明其复杂度上界为[tex]O(n\log^2 n)[/tex]。

  现在证明preferred child的更改次数是均摊[tex]O(n\log n)[/tex]的,首先我们知道一次access最多让[tex]O(\log n)[/tex]条轻边变为preferred edge,然而重边一次却会有很多变为preferred edge,那么复杂度就是重边变为preferred edge的次数,而重边变为preferred edge的次数级别等于重边从preferred edge变为非preferred edge+所有边【即n-1】,那么复杂度就是重边从preferred edge变为非preferred edge的次数,对于一条重边,变为非preferred edge以后,意味着有一条轻边变为preferred edge【或者preferred edge消失,这种情况最多只有[tex]O(q)[/tex]个,q为access次数,所以可以忽略】,于是重边从preferred edge变为非preferred edge的次数至多为轻边变为preferred edge的次数,而轻边变为preferred edge的次数显然是[tex]O(n\log n)[/tex]的,得证。

  其实到这里就可以引入TopTree了,为了完整顺便把splay维护的LCT复杂度是[tex]O(\log n)[/tex]也证了。

  现在证明splay维护的LCT复杂度是[tex]O(\log n)[/tex]的,首先splay的单次旋转的复杂度是均摊[tex]O(\log sz_{root}-\log sz_{x})[/tex],root是splay的根,x是提根的节点,[tex]sz_x[/tex]是x子树大小。这个复杂度的证明详见splay的复杂度证明,证明涉及对双旋splay的每一种操作的分析,通过缩放最后还有3的常数,非常麻烦,这里不证了。

  然后我们代入access中分析,很容易发现中间的加减相互抵消了,最后的复杂度是均摊[tex]O(\log n-\log sz_x)[/tex]。

  至此我们完成了LCT的复杂度分析。

Top-Tree的操作分析

  那么我们要维护子树信息,该怎么办?

  preferred child的更改次数是均摊[tex]O(n\log n)[/tex],这个性质非常优秀,很多动态树题目都通过这个性质来维护各种信息,TopTree也是这样。

  考虑在access的时候顺便维护轻儿子的信息,这样就可以动态维护子树信息了。

  说白了TopTree其实就没了,因为剩下的就是子树和链之间互相影响的细节了,好好地写一下就能自己处理掉了。

  

  如果儿子无序,那么我们可以直接维护一个二叉树来维护那些轻儿子,如果儿子有序,那么同样可以维护一个BST来维护轻儿子。

  每次access进行preferred child更改的时候,考虑轻重边的更改,把要变成轻儿子的重儿子加入维护轻儿子的数据结构,把要变成重儿子的轻儿子从维护轻儿子的数据结构中拿出,放入LCT本身有的维护链的splay中。

  这样就完成了access操作,但是打标记的时候会特别恶心,但是无论如何,遵循“轻重分开”的原则进行维护一定没有错的,也就是子树信息管子树信息维护,链信息管链信息维护,当然根据需要,有时候子树信息需要加到链信息上去维护。

  【然后sone1的10kb就是这样出来的= =。。】

  【怎么样,sb吧。。】

Top-Tree的复杂度分析

  关于LCT原有部分复杂度无需证明了,所需要证明的就是维护轻儿子的复杂度。

  【窝还不会TAT。。。感觉应该还是从preferred child变换次数证起,证变换次数和度数的关系,由此得到维护轻儿子复杂度】


Euler-Tour-Tree

简介

 一种从简到烦皆可的维护树形态的数据结构,现先讲Euler-Tour序。

  可分需要有好几种写法:

    1.不省略Euler-Tour序

    2.省略Euler-Tour序为单括号dfs序

    3.省略Euler-Tour序为括号匹配dfs序

    4.据说还可以把一个点拆成六个点,并且也能实现换根,表示不清楚。

  其中第一种一般不用于动态树维护。

不省略Euler-Tour序

 感觉就只能方便求LCA了,可以比较轻松地做到[tex]O(n\log n)-O(1)[/tex]在线不修改求LCA,ST表记深度即可。

  经测试这玩意跑特快,蛮有实用价值的,比那啥[tex]O(n)-O(1)[/tex]LCA有用。

  不过和本主题无关。

省略Euler-Tour序为单括号dfs序

 一般只是下一种实现方法的简略版,如果我们不需要链信息,可以不记录括号匹配。

省略Euler-Tour序为括号匹配dfs序

 可支持基本操作:

   1.子树操作

   2.换父亲

   3.链询问

  以上操作直接使用BST维护dfs序即可,复杂度均为[tex]O(n\log n)[/tex]。

  通过和LCT结合可以把复杂度提升一个[tex]\log n[/tex]来换取链修改的功能。

基本操作:access

  在LCTaccess的时候把重儿子表示的子树dfs序拼接到父亲表示的dfs序首,这样就能通过[tex]O(\log^2n)[/tex]的时间得到一个点到根这么一条链上的连续信息。

  复杂度[tex]O(n\log^2n)[/tex]

  这样我们可以实现链修改了。

  然而相较TopTree,如何实现换根?

换根

  这种换根方式参考松爷的方式,在ZJOI2015day1的课件中有提及。

  我们考虑不管括号匹配的左右关系,如何换根。

  那么我们只需要把需要换根的节点x access,然后如下图。

  设access以后x所处位置是p,那么reverse(1,p),reverse(p+1,n*2)

  这样关系就对了,但是那些红边连向的子树内部左右括号全反了,怎么办呢。

  也很简单,直接在LCT上打个标记,下次遇到的时候直接把子树翻转回来就行了,不过这样链询问的复杂度也变为了[tex]O(n\log^2n)[/tex]【这么说起来直接写单括号算了】

  复杂度当然也是[tex]O(n\log^2n)[/tex]

  至此,ETT基本完成了TopTree的所有操作,只不过。。复杂度多了一些。。事实上,他跑得确实比TopTree慢。

  Q:所以说这种数据结构并没有什么卵用?

  A:不!他能衬托TopTree是有用的!


树上动态联通块问题

引入

 我们从一个经典的问题开始。

  QTREE7:每个点有黑白两种颜色。三种操作。

    1.单点修改颜色

    2.单点修改权值

    3.询问连通块最大权值

  解法有很多,我现在比较了解的有两种。

  1.TopTree强行维护异色子树信息,涉及link、cut

  2.既然TopTree可行,我们可以考虑ETT的思路,利用dfs序,方法如下:
    显然,一个连通块是可以用dfs序表示的,那么将一个节点的信息存于其深度最低的与其异色的祖先内【根节点特判】,也就是说每个节点存着异色子连通块信息,设这个信息为S(x)

    考虑修改节点x的颜色的时候如何操作:

      1.首先将dfs序中其同色连通块儿子取出,变为新的S(x),将原本的S(x)塞入该节点同色连通块的dfs序中。

      2.如果修改节点颜色后颜色与其父亲不一致,那么先前其一定在非直接父亲的祖先的S(x)内,那么从那个祖先内取出,存入直接父亲的S(x)内。若修改节点颜色后颜色与其父亲一致,那么先前其一定在直接父亲的S(x)内,从中取出存入直接父亲所在连通块的dfs序中。

  这样我们就成功动态维护了dfs序,dfs序都维护了,max当然不在话下。

 

  如果我们把点修改颜色,换成链修改颜色呢?

  我们把问题一般化:链修改+维护联通块dfs序

Link-Cut-Memphis

简介

  一种解决树上动态联通块链修改问题的方式。

  不知道该叫什么,那就大言不惭地和校内人一起叫LCM算了。

正文

 ①首先明确一下链修改=一个点到根路径上一个点的区间修改,很显然,找出LCA就行了

  ②并且在这个区间里,设每个节点颜色为[tex]a_1,a_2...a_N[/tex],对于[tex]1<=i<N,a_i\not=a_{i+1}[/tex],我们称为一个颜色更变处,设每次操作i经过[tex]cnt_i[/tex]个颜色更变处,那么[tex]\sum{cnt_i}[/tex]是[tex]O(m\log n)[/tex]级别的,复杂度证明同LCT的preferred-child更变次数的证明。

 明确了以上两点后,我们回顾一下QTREE7的解决方法。

  首先是Top-Tree,我认为直接上是不能做的,至少我不会,sone爷也不会。

  顺着方法2的思路,当然直接上也是不能做的,但是可以看看方法2都维护了什么:

   异色子联通块信息

  Q:为什么要维护这个东西? A:为了方便维护一个点颜色翻转后处于什么联通块这一需求。

  如法炮制,我们知道了②,也就是说暴力求该每个相同的颜色段复杂度是对的,所以我们要维护一条同色链颜色翻转后处于什么联通块。所以,我们需要维护的不仅仅是子联通块了,我们还需要更多。

  现颜色以红色和黑色为例,比如有这么一棵树

  最上面的是根,一条边的颜色表示他所连的儿子的颜色,很显然下面这是一个联通块【黑色框框】,定义这个联通块为1号联通块,同样的,我们定义下面四个分隔开的红点为四个联通块,从左到右依次标号为2、3、4、5,最下面的两个为6、7。

  我们定义黑色框框部分是1号联通块的主树。

  但是,我们为了满足要求,我们还需要维护这个【蓝色框框】

  我们定义蓝色框框的这棵树(看下去就知道是树)为1号联通块的辅树。

  可以这样定义:

   1.一个维护同色联通块信息,可视为一个dfs序表示的同色联通块,称之为主树

     ——用来维护一条链不变颜色,处于哪个联通块

   2.一个维护异色联通块信息,可视为一个LCT串起来的异色子联通块的dfs序,称之为辅树

     ——用来维护一条链变了颜色,处于哪个联通块

  注意:一个联通块的主树是构成其父联通块的辅树的一部分

 

  按照一开始的分析,现在的目标是同色联通块的块内链修改操作,颜色交接处均摊是[tex]O(\log n)[/tex]的。

  *定义expose操作为access操作在辅树上的变种操作:

  expose一个点,将其到该联通块顶端打通,然后将所有异色联通块dfs序串起来。

  *定义expose后所发现的联通顶端节点为关键节点。

  expose后将该联通块辅树关键节点所在dfs序接入关键节点父亲所在的主树中,和父联通块主树合并;相对的,将主树中的关键节点从关键节点父亲的辅树中该父亲节点所代表的异色子联通块dfs序中切除,成为父联通块辅树的一部分。

  至此,我们可以发现通过expose及其之后的操作,使得该联通块的一条链完成与父联通块的合并,并且原本的主树变为辅树,辅树变为主树。

  思路大致明朗。

 

  所谓链修改操作即为将一个节点到根上的一段进行主树和辅树的相互变换。

  当然还有很多细节,比如根节点所在联通块要特判之类的。

 

  复杂度是[tex]O(n\log^2 n)[/tex]的,别和谈常数!

  在BZOJ 3914: Jabby's shadows中,我用了树链剖分记录一个点的颜色。

 

  至此我们可以维护链修改+维护联通块dfs序了。

  之后我经过脑补,链翻转应该也是可以实现的,但是那样复杂度就不知道了,因为链翻转联通块颜色交界处的个数我不会统计囧。

  顺便讲一下在BZOJ 3914,至于dfs序维护联通块直径的做法可以参考ZJOI捉迷藏。



 

以上
  
Category: Data Structure | Tags: data structure The End | Read Count: 7026
Avatar_small
wangyisong said:
Sat, 08 Aug 2015 00:15:11 +0800

膜膜膜!...窝什么都不会

Avatar_small
negiizhao said:
Sat, 31 Mar 2018 22:25:59 +0800

我猜top tree能log时间淦链修改。。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com