lowest_common_ancestor.html

<!--
    数記事書いて飽きて放置されてた my wiki (ローカルに作って公開はされていない) からコピペしてきた
-->

<title>Lowest Common Ancestor</title>
<p>
<b>lowest common ancestor</b>(<b>LCA</b>)とは、根付き木の2つの頂点に対して、共通祖先(common ancestor)のうち最も深さが深い頂点のこと、またそれを求める問題のことである。
<b>最小共通祖先</b>, <b>最小共通先祖</b>, <b>nearest common ancestor</b>, <b>NCA</b>, <b>最近共通祖先</b> などとも呼ばれる。
</p>
<p>
クエリ問題版では、前処理に$Θ(n)$・クエリが$Θ(1)$時間の2つのアルゴリズム、"Euler tourによる±RMQへの還元"や"Schieber-Vishkin algorithm"などが知られている。
</p>

<h3>定義</h3>
<p>
根付き木$T = (V, E, root)$, 頂点$v, u \in V$に対して、
$$
LCA_{T}(v, u) = \underset{a \in V, ancestor(v, a) ∧ ancestor(u, a)}{\operatorname{arg\,max}} depth(a)
$$
を$T,v,u$のLowest common ancestorという。
</p>

<h4>クエリ問題</h4>
<p>
根付き木が事前に与えられる。
クエリでは前処理結果と2つの頂点が与えられて、入力のLCAを求める。
</p>
<h4>動的問題</h4>
<p>
根付き木に対して初期状態を求める。
LCAクエリでは内部状態と2つの頂点が与えられて、入力のLCAを求める。
</p>
<h4>パラメータ</h4>
<ul>
<li>$n$ = 木の頂点数</li>
</ul>

<h3>アルゴリズム</h3>
<h4>ダブリングアルゴリズム</h4>
<p>
それぞれの頂点が$2^k$番目の"k-親"への参照と深さを保持する。クエリでは、2つの頂点の祖先の深さを比較しながら処理をする。{{要加筆}}
</p><p>
クエリ問題版に対して、前処理$Θ(n\log n)$時間, $Θ(n\log n)$空間, クエリ$Θ(\log n)$時間を達成する。
</p>

<h4>パスへの分割</h4>
<p>
"パスへの分割(木)"をする。クエリでは、パスの深さを比較しながら上っていき、同じパスに到達したら終了する。
</p><p>
クエリ問題版に対して、前処理$Θ(n)$時間, $Θ(n)$空間, クエリ$Θ(\log n)$時間を達成する。
</p><p>
動的問題版に対しては"link-cut tree"を用いることでクエリならし$Θ(\log n)$時間を達成する。
</p>

<h4>"euler tour"による<a href='range_minimum_query#plusminus-rmq'>±RMQ</a>への還元</h4>
<p>
"euler tour#頂点記録版"を用いて頂点の列を作る。頂点と一緒に深さも記録する。さらに、頂点に対して列中での一番左・右の出現位置L,Rをそれぞれ記録する。
このとき、頂点v,uのLCAは列中でv,uの出現を全て含む極小の区間、つまり$[L_v, R_u]$もしくは$[L_u, R_v]$の中で深さが最小である頂点である。この列の深さ情報は隣接する2つの要素の差が必ず±1になるので、それを利用できる。
±1の制約を使わずに単なる"range minimum query"と考えることもできる。
</p><p>
クエリ問題版に対しては"±RMQ#アルゴリズム"を用いることができ、前処理$Θ(n)$時間, クエリ$Θ(1)$時間を達成する。
</p><p>
動的問題版に対しては"euler tour tree"を用いることで様々な操作をサポートしてクエリ$Θ(\log n)$時間を達成できる。{{要加筆}}
</p>
<h4>Schieber-Vishkin algorithm</h4>
<p>
"Schieber-Vishkin algorithm"を用いることで、クエリ問題版に対して前処理$Θ(n)$時間, クエリ$Θ(1)$時間を達成する。
</p>