【转】动态树入门

背景

树剖大概算是入门了,树上乱搞系列直径,重心,树剖,分治,倍增等)可以说都是一种思想,一种手段,而不是一种数据结构。

树剖通过树上面划分链,在链上静态操作(使用线段树,树状态数组,主席树等等工具),实现两点路径上值改变,最值查询,和查询,第k大查询(对象可能是点,可能是边)等功能。

但是如果轻重链会改变,如link两个点,cut两个点(有可能是森林或者树,反正无环),难以维护静态操作,就需要动态树或者其他方式来剖分。

 

推荐

看来不少的博客,大都勉勉强强,论文也不是很懂,GG。下面这两个慢慢看,终于,emmmm

第一个博主,很良心的帖子,但是没有看清楚说的哪个是原树还是splay树。

           https://oi.men.ci/link-cut-tree-notes/

第二个,比较清楚,分清楚了原树和slapy树(辅助树),就好理解了。

          https://www.cnblogs.com/BLADEVIL/p/3510997.html

 

个人的补充

难死了。。。。。刷下水题转一下注意力。

原文地址:https://www.cnblogs.com/hua-dong/p/8109143.html