首页 > 其他 > 详细

【转】动态树入门

时间:2017-12-26 11:16:56      阅读:254      评论:0      收藏:0      [点我收藏+]

背景

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

树剖通过树上面划分链,在链上静态操作(使用线段树,树状态数组,主席树等等工具),实现两点路径上值改变,最值查询,和查询,第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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!