Tree資料結構: Heavy-Light Decomposition

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:正向經過邊,列出原權重;反向經過邊,列出加了負號的權重。

運用前述的資料結構儲存此數列。樹上一條由淺到深的路徑的權重,即是區間和:參照節點的遍歷順序,較淺節點的首度拜訪時刻,作為區間左邊界;較深節點的首度拜訪時刻減一,作為區間右邊界。從路徑分枝出去的多餘子樹,在區間和之中出現兩次、正負相消,最後剛好剩下路徑的權重。

想要查詢任意一條路徑的權重,就從LCA切斷路徑,得到兩條路徑,都是由淺到深。兩條路徑分頭計算區間和,再相加,即是原路徑的權重。

時間複雜度

DFS為O(V),建立長鏈的資料結構為O(VlogV),查詢LCA為O(logV),查詢一條路徑為O(logV)。

Heavy-Light Decomposition

遍歷時,優先走向最大的子樹。所有長鏈皆是連續區間。

Dynamic Graph資料結構: Euler Tour Tree

Euler Tour Tree

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides08.pdf

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides09.pdf

UVa 11998