Tree 资料结构: Heavy-Light Decomposition

发布于 2025-01-31 22:20:40 字数 3037 浏览 0 评论 0 收藏 0

Heavy-Light Decomposition

想查询一棵树上任意一条路径的权重，直觉就得到一个 O(V) 方法，最差情况是这棵树恰为一条长链。

长链有很棒的资料结构。只要找出树上所有长链，每条长链套用伪线段树、BIT、Sparse Table、BST、Heap，就能降低时间複杂度。

找长链怎麽找呢？先用一次 Graph Traversal 算出每棵子树有多少节点。然后，树上每个节点各自连向最大的子树。最后，自然形成了链，树上每个节点都隶属于某条链。

这种分割一棵树成为数条链的手法，称作“重轻分解”。中文网路上意译为“树链剖分”。

由根往叶走，一旦遭遇新链，新链子树小于等于原链子树，剩下的节点数量不到一半，沿途最多遇到 logV 条链。一条路径藉由 LCA 拆成两段，沿途最多遇到 2logV 条链。

时间複杂度

一条链最多 V 个点，一条链实施区间查询为 O(logV)。一棵树最多 V 条链，但是一条路径最多只遇到 2logV 条链、实施 2logV 次区间查询。

树链剖分为 O(V)，建立所有长链们的资料结构为 O(VlogV)，查询 LCA 为 O(logV)，查询一条路径为 O((logV)^2)。

Timus 1553 Sphere QTREE ICPC 4960 UVa 12424

Dynamic Trees 资料结构: Link-Cut Tree

Link-Cut Tree

http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf
http://courses.csail.mit.edu/6.851/spring07/scribe/lec04.pdf
http://wenku.baidu.com/view/75906f160b4e767f5acfcedb.html
http://hlworld.diandian.com/post/2012-03-26/17452276
http://www.shuizilong.com/house/archives/tag/动态树/

一、静态树：甲、一棵无向树。
        　　乙、更新一个点（边) 的数值。
        　　丙、查询一条路径的最大值、最小值、总和、相异数字数量、......。
二、动态树：丁、一棵树，砍断一条边，变成两棵树。
        　　戊、两棵树，增加一条边，接成一棵树。

动态树部分，由于长链可能会被切断的，所以“树链剖分”就没搞头了。
就只能老老实实的用 Link-Cut Tree 了。

http://hi.baidu.com/yy17yy/item/465649279358993395f62b59

改变树根位置的 link-cut tree
反转所有原树根到新树根 x 的边
先 access(x)，此时 x 会是 splay tree 的树根，
然后颠倒整棵 splay tree 的左右小孩即可
运用反转标记就简单多了

改变树根位置之后
就可以简单的得到一条路径 ab：先 makeroot(a)、然后 access(b) 即可。

UVa 11994

Tree 资料结构: Euler Tour Technique

Euler Tour Technique

想查询一棵树上任意一条路径的权重，直觉就得到一个 O(V) 方法，最差情况是这棵树恰为一条长链。

长链有很棒的资料结构，只要套用伪线段树、BIT、Sparse Table、BST、Heap，就能降低时间複杂度。

树一般不是长链，那麽要怎麽把树变成长链？树根为起点，实施 DFS，依照遍历顺序，列出每一条边（点）的权重，得到一条数列，长度为 2E：正向经过边，列出原权重；反向经过边，列出加了负号的权重。