树剖学习笔记

咕了好几场cf的题解,想补可是有点懒。。。

前排膜拜dalao Orz

发一篇树链剖分的学习笔记吧,其实我的树链剖分是一位大佬手把手教我的,自己学的时候感觉什么都看不懂,什么重儿子,什么重链之类的完全不知道有什么用,当然现在差不多懂了,然后我就稍微总结了一些,要求重儿子,重链就是取出来一条,一条最长的连比如再做LCA的题的时候就可以先以链为单位跳了,所以就不需要用倍增那样一下一下的跳上去,至于最坏的清空也只是多跳几条连而已,当然两个结点离得很近是存在一个一个结点跳的,不过时间复杂度并不高,因为两个点很近。。。

树剖全称是树链剖分,也就是能剖出来一条链,所以如果我们以这个链做一下思考,显然可以用线段树维护(:逃

不过放些问题,因为直接从树上剖下来得到的一条链的编号可能不连续的,所以我们先引入一个概念。

重儿子,对于一个点来说如果以他儿子为根的树深度比其儿子构成树的深度大的话,那这个就是重儿子,如果存在两个深度相同的话,那样随便选一个称为重儿子,显然对于一个结点来说重儿子唯一

我们放到线段树上去维护区间编号就是一个dfs序,不过遍历儿子需要从重儿子开始遍历,其他无所谓了

然后每个结点的重儿子连起来就会形成一个重链,右图红色的线就是重边(父亲和重儿子相连的边)

这样我们如果要是修改两个节点之间的值会很简单的去分成若干条重链,这样我们之前用的dfs序是先遍历 了重儿子所以保证了两点

1.dfs序遍历可以得到一条编号相连的链,这样就可以用线段树维护一条链的值了,因为我们吧树拆成了一条一条重链,和一些散的结点,然后用线段树去维护

2.dfs序遍历回此节点时得到的编号是儿子门最大编号,这样就可以直接用线段树去维护一颗树的值了

当然树剖弄出来一条链所以理所当然可以求LCA,方法比树上倍增强很多,至少不用一步一步跳了,

注意事项:

1.这样一条一条的跳不是跳到链首而是跳到链首的父亲上

又想起学倍增的时候的那只小兔子了。。。

所以先总结一下树剖主要的步骤

1.求重儿子,重链

2.编号,这个编号是映射到线段树的编号,当然还要映射回来

3.维护线段树

4. 。。。好像没了

发现自己写的好少,可能和我还理解不清楚有关系吧,毕竟我才写了一道模板题就来些博客了 。。。。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注