クエリ先読みする場合の LCA を線形時間で解きます。何日か前に TL で話していたら思いついたので。
まずそのときのツイートをいくつか貼ります。
LCA ってクエリ先読みして DFS とかの方針で線形で解ける? わかりません
— えびちゃん (@rsk0315_h4x) 2022年3月27日
UnionFind をなんかいい感じに弄ると Tarjan の offline LCA が線型になるらしいです。https://t.co/TSCy3cIwgS
— みさわ (@Mi_Sawa) 2022年3月27日
特殊な集合だと union-find が O(1) になったりする系のやつ、例の usize_decremental_set とかのやつでもあったね
— えびちゃん (@rsk0315_h4x) 2022年3月27日
あれ、もしかして同じか?
— えびちゃん (@rsk0315_h4x) 2022年3月27日
Euler tour みたいな感じで見ると区間になってるはずなので
— えびちゃん (@rsk0315_h4x) 2022年3月27日
tarjan's offline LCA の DFS における pre-order で頂点を並べるとそれでいけそう
— 熨斗袋 (@noshi91) 2022年3月27日
クエリ先読みしなくても線形 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) == 6
、lca(4, 8) == 1
、lca(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 解説 などを参照。
- A = {1, 2, ..., n} で初期化
— えびちゃん (@rsk0315_h4x) 2021年5月2日
- A ← A \ {i} を O(1) 時間
- A の要素の列挙を O(|A|) 時間
みたいなの、ふと思いついたけどそこまで用途ないねとなった
- A = {1, 2, ..., n} で初期化
— 熨斗袋 (@noshi91) 2021年5月2日
- A ← A \ {i} を O(1)
- min { x ∈ A | x > i } を O(1)
ならギリ需要ありそう
X 点 Y クエリだと α(X)/query と書かれがちですが、さらに精密には α(Y, X)/query になっていて、Y が X に比べて大きいと (特に Y > X log(X) だと) α(Y, X) = 1 になります。
— 熨斗袋 (@noshi91) 2021年5月3日
よって、できました。
こうしたデータ構造を持っていなくても、C++ で言うところの std::set
などを使うと、\(O(n+q \log(n))\) 時間になります。
実装
あんまり定数倍のことは気にしていません。これから考えるかもしれません。
おわり
みんな大好き熨斗袋。もちろんえびちゃんも大好きです。