二分ライフティングを使った祖先テーブル入門：LCAとk-th祖先をO(log N)で解く実装解説

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

イントロダクション：祖先テーブルとは何か

「祖先テーブル」（ancestor table、あるいは binary lifting テーブル）は、木（ツリー）構造における各ノードの 2^k 上位（祖先）を高速に求めるための前処理データ構造です。競技プログラミングやアルゴリズム設計で広く用いられ、特に「k 個上の祖先を求める」「Lowest Common Ancestor（LCA、最近共通祖先）を高速に求める」問題で役立ちます。

概念の要点

  • 木の各ノード v について up[0][v] を直接の親（parent）とする。
  • 一般に up[j][v] を v から 2^j 上に上がった先の祖先と定義する。したがって再帰的に
    up[j][v] = up[j-1][ up[j-1][v] ]（存在しない場合は -1 などの無効値）となる。
  • この表を前処理で構築しておけば、k を二進展開して該当するビット分だけ上れば k-th ancestor を O(log N) で求められる。
  • LCA も深さ調整＋二分ライフティングで O(log N) で計算可能。

なぜ有用か（利点）

  • 前処理 O(N log N)、各問い合わせ O(log N) として非常に高速（N はノード数）。
  • 実装が比較的簡単で、メモリは O(N log N) だが定数が小さく扱いやすい。
  • k-th ancestor や LCA、木上での距離計算などの基盤となる操作を効率化できる。

基本アルゴリズムと実装方針

典型的な実装フローは次の通りです。

  • 1) 深さ優先探索（DFS）や幅優先探索（BFS）で各ノードの深さ depth[v] と up[0][v]（親）を求める。
  • 2) LOG = ceil(log2(maxN))+1 を決め、up[1..LOG-1][v] を再帰式で埋める。
  • 3) k-th ancestor：k の各ビットを走査し、対応する up[j] を辿る。
  • 4) LCA：深さをそろえた後、上位のビットから同時に lift し、最終的に up[0] を返す。

主要な計算量

  • 前処理：O(N log N)
  • 1回の k-th ancestor クエリ：O(log N)
  • 1回の LCA クエリ：O(log N)
  • メモリ使用量：O(N log N)

代表的な C++ 実装（概念を示す簡潔な例）

以下は典型的な二分ライフティングを用いた LCA と k-th ancestor の実装例です（0-indexed）。WordPress に貼る場合は <pre><code> タグで囲うと見やすくなります。

// N: ノード数, LOG: 上限（例: ceil(log2(N))+1）
vector> up(LOG, vector(N, -1));
vector depth(N, 0);

// DFS または BFS で depth と up[0] を設定
void dfs(int v, int p){
    up[0][v] = p;
    for(int to : adj[v]){
        if(to == p) continue;
        depth[to] = depth[v] + 1;
        dfs(to, v);
    }
}

// テーブル構築
for(int j = 1; j < LOG; ++j){
    for(int v = 0; v < N; ++v){
        int mid = up[j-1][v];
        up[j][v] = (mid == -1 ? -1 : up[j-1][mid]);
    }
}

// k 個上の祖先
int kth_ancestor(int v, int k){
    for(int j = 0; j < LOG && v != -1; ++j){
        if(k & (1 << j)) v = up[j][v];
    }
    return v;
}

// LCA
int lca(int a, int b){
    if(depth[a] < depth[b]) swap(a,b);
    int diff = depth[a] - depth[b];
    a = kth_ancestor(a, diff);
    if(a == b) return a;
    for(int j = LOG-1; j >= 0; --j){
        if(up[j][a] != up[j][b]){
            a = up[j][a];
            b = up[j][b];
        }
    }
    return up[0][a];
}

実装上の注意点・落とし穴

  • LOG の取り方：LOG = floor(log2(N))+1 で十分ですが、余裕を持って 20〜30 を固定することも多い（N ≤ 2e5 なら 20〜18 付近）。
  • 根（root）や森林（複数の連結成分）の扱い：親が存在しないノードは -1 などで扱い、DFS をすべての未訪問ノードから行っておく。
  • k が深さを超える場合：kth_ancestor が -1 を返すように実装しておき処理を止める。
  • スタック深さ：再帰 DFS を用いる場合、N が大きいとスタックオーバーフローする可能性があるため、BFS や明示的なスタックを推奨する場合もある。
  • 1-indexed と 0-indexed の混同に注意する。配列初期化も忘れずに。

応用例と派生テクニック

祖先テーブルは次のような場面で使われます。

  • 最近共通祖先（LCA）を利用した木上の距離計算（dist(u,v) = depth[u] + depth[v] - 2*depth[lca(u,v)]）。
  • k 個上の祖先を求める問題（クエリで任意の k が与えられる）。
  • 木の移動シミュレーションや ancestor-based DP（木 DP で高速に遡る必要がある場合）。
  • 重心探索や up-sweep/down-sweep 系のアルゴリズムでの高速な親アクセス。

他の手法との比較

  • Euler Tour + RMQ（スパーステーブル）: LCA を O(1) で答えられる手法（事前 O(N log N) または O(N) 構築）。クエリ回数が非常に多い場合に有利。だが k-th ancestor 単体のクエリでは直接的ではない。
  • Tarjan のオフライン LCA: オンラインではなく、事前に全クエリが分かっている場合にほぼ O(N + Q α(N)) で処理できる（Disjoint Set Union を使用）。
  • 動的木（Link-Cut Tree 等）: 木がリンク・カットで動的に変わる場合は祖先テーブルは向かない。動的な更新をサポートしたデータ構造が必要。
  • Heavy-Light Decomposition (HLD): 距離やパス上の区間クエリと合わせて祖先操作を行う際に便利。LCA は HLD で O(log N) で求められる。

実際の利用上のコツ

  • LOG を固定値にしておくと実装が簡単（例: 20–30）。ただし N が非常に大きい場合は計算してから確保する方がメモリ効率良い。
  • 複数の root を扱うときは、各 root の depth を 0 にしておくと扱いやすい（必要に応じて root の parent を -1 に）。
  • 配列やベクタの初期化は忘れずに（-1 初期化など）。単純なバグの原因となりやすい。

まとめ

祖先テーブル（二分ライフティング）は、木構造に対する基本かつ強力な前処理テクニックです。前処理 O(N log N) で k-th ancestor や LCA を O(log N) に抑えられるため、多くの問題で有効です。実装は比較的単純で、深さ配列と up テーブルを正しく初期化することがポイントになります。クエリ数や木の動的性質に応じて Euler Tour + RMQ、Tarjan 法、Link-Cut Tree などの別手法と使い分けるとよいでしょう。

参考文献

カテゴリー
IT
前の記事
非負辺重みとは何か？定義と直感、Dijkstra・Bellman–Ford・Johnsonで読み解く最短経路アルゴリズムNew!!
2025年11月20日
次の記事
経路列挙とは何か？ネットワーク・Webアプリ・ファイルシステムの技術と対策を徹底解説New!!
2025年11月20日