← 返回首頁

Binary Lifting & LCA 二進制提升

樹結構

2^k 祖先表 (up[node][k])

演算法說明

Binary Lifting 預處理每個節點的 2^k 祖先,用於在 O(log N) 時間內回答 LCA 查詢。

步驟:1. 計算每個節點的深度 2. 預處理 up 表 3. 查詢時先對齊深度,再同步向上跳