\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年8月31日 星期一

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表,pa[i][x]表示x的第\(2^i\)的祖先,若不存在則為\(-1\),可以在DFS或BFS的過程中求得,複雜度為\(\ord{N*MAX\_LOG}\)

對於每筆詢問,我們可以利用剛剛求得的倍增表,在\(\ord{MAX\_LOG}\)的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度,之後二分搜LCA的位置
附上模板:

沒有留言:

張貼留言