[关闭]
@Bei-S 2019-01-10T07:20:36.000000Z 字数 713 阅读 602

动态树(Link-Cut-Tree)学习笔记

数据结构


Death is what gives life meaning.


初识LCT是高一下学期开学没多久,
当时的自己非常颓废,天天看小说,刷知乎
导致那一段的知识点到现在非常薄弱。

还记得当时三位省队神仙给我们连着讲树剖,线段树,后缀数组,Ac自动机,LCT...头都大了

时至今日,必须要学会上述NOIP不怎么考的知识

正文:

动态树问题通常要求维护一个有根树森林,不仅支持树链剖分的链修改和查询,而且支持树的合并,分裂和更改树根的操作。(大部分情况下,动态树问题不要求子树查询和修改操作)
动态树和重链剖分类似,也需要维护树的轻重链信息,但是重链剖分所维护的树的结构是不会变化的,所以可以用线段树来维护,而动态树的操作则需要更加灵活的区间数据结构,一般通过平衡树实现。

因为动态树的形态会变化,所以按子树大小划分轻重儿子的方法是错误的。我们人为规定每次将访问的点到根的路径变成一条重链(与Splay思想类似,每次访问过一个点之后将其旋转至根),可以证明这样规定可以保证轻重儿子切换次数为均摊O(𝑙𝑜𝑔𝑛)次(证明见下文)。通过恰当的实现,Treap可以做到O(𝑛𝑙𝑜𝑔^2 𝑛)的复杂度,而Splay则可以做到O(𝑛𝑙𝑜𝑔𝑛)的复杂度

对于动态树来说,我们只用维护一个fa数组,如果一个节点是其所处Splay的根,那么其fa表示在树上与Splay所处重链上深度最小节点相连的父亲节点(因为Splay的根不一定是深度最小的节点,所以这个fa不一定与Splay的根相连),否则表示其在Splay中的父亲节点(由于Splay的深度序是中序遍历,所以这个节点与其fa也不一定相连)。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注