樹における最近共通祖先の効率的計算手法
木構造上の2頂点間の最近共通祖先（Lowest Common Ancestor, LCA）を高速に求めるには、複数のアルゴリズムが存在します。本稿では、倍増法、オイラー巡回＋RMQ、および木の重軽分解（Heavy-Light Decomposition）の3つの代表的手法について、それぞれの設計思想・実装構造・計算量特性を解説します。
倍増法によるLCAクエリ
各頂点から根方向へ2kステップ先の祖先とその ...
8月5日 03:47 投稿