\( \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 Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平,然後紀錄當前節點u的深度在dep[u],紀錄時間戳記,進入的時候要紀錄一次,出來的時候也要記錄,把當前點u進入的時間戳紀錄在in[u]中,時間戳的大小為2*n,所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中,最小深度的時間戳經過的那個點
查詢:
RMQ的部分就要自己維護了,使用線段樹效能會非常差,在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

沒有留言:

張貼留言