えびちゃんの日記

えびちゃん(競プロ)の日記です。

オフラインの線形時間 LCA

クエリ先読みする場合の LCA を線形時間で解きます。何日か前に TL で話していたら思いついたので。

まずそのときのツイートをいくつか貼ります。

niuez.github.io

クエリ先読みしなくても線形 RMQ を使えば線形時間で解けますが、それはそれです。

定義

念のため。

LCA (lowest common ancestor) problem は次のような問題です。

  • まず根を \(r\) とする \(n\) 頂点の木が与えられて、クエリが \(q\) 個与えられます。
  • \(i\) 個目のクエリ \( (u_i, v_i)\):\(u_i\) と \(v_i\) の両方の祖先である頂点のうち、\(r\) から最も遠い頂点を出力せよ。

クエリ先読みというのは、「クエリを順に読んで一つずつ処理する」のではなく、「クエリを一通り先に読み、まとめてそれらを処理する」という解法の総称です。

オフラインというのはそうした解法を許容する問題設定(あるいはそうしたアルゴリズムも指す)で、そうでないものはオンラインと呼ばれます。競プロにおいてオンラインアルゴリズムが想定とされる(+ オフラインは許容したくない)場合は、インタラクティブ問題として出題されたり、「\(i\) 番目の出力と \(i+1\) 番目の入力の xor を実際の \(i+1\) 番目の入力値とする」などの問題設定で出題されたりします。

解法

まず、適当に DFS するなどしておいて、頂点の番号を pre-order(最初に訪れた順)に振り直しておきます。ここまでは簡単に \(O(n)\) 時間でできます。

      0
     /  \
    1    9
   / \
  2   6
 /|\  |\
3 4 5 7 8

そして、頂点 \(i\) に対応する値 \(a_i\) を管理しながら DFS します。 \(a_i\) は \(1\) で初期化しておき、DFS をして \(i\) から親に帰るとき \(a_i \gets 0\) で更新します。

たとえば、8 に到着した時点の \(a_i\) の値は次のようになります。

      1
     /  \
    1    1
   / \
  0   1
 /|\  |\
0 0 0 0 1

自分より先に訪れた頂点について、自分の祖先であれば 1、そうでなければ 0 になっていることがわかります。

また、表の形式で書くと次のようになります。

i:    0 1 2 3 4 5 6 7 8 9
a[i]: 1 1 0 0 0 0 1 0 1 1

今いる頂点 (8) とそれ以前に訪れた頂点 i について、lca(i, 8) は「(その時点の)a において、j <= i && a[j] == 1 となるような最大の j」、すなわち「i より左(i 含む)に 1 が現れる最も右の位置」となっています。

たとえば、lca(7, 8) == 6lca(4, 8) == 1lca(0, 8) == 0 です(表と木を見比べてみましょう)。lca(9, 8) はこの時点ではまだわかりません。

さて、これらの処理を行うために、以下の処理を \(O(1)\) 時間でできるデータ構造があればよいです。

  • \(a_i \gets 1\) (for all \(i\in[0, n)\)) で初期化。
  • \(a_i \gets 0\) (for given \(i\))で更新。
  • \(\max\,\{j \mid j\le i \wedge a_j = 1\}\) (for given \(i\))を報告。

そういうデータ構造はあります。ABC 228 D 解説 などを参照。

よって、できました。

こうしたデータ構造を持っていなくても、C++ で言うところの std::set などを使うと、\(O(n+q \log(n))\) 時間になります。

実装

judge.yosupo.jp

あんまり定数倍のことは気にしていません。これから考えるかもしれません。

おわり

みんな大好き熨斗袋。もちろんえびちゃんも大好きです。