え、[0, n) の整数からなる順列の LIS って O(n log(log(n))) 時間でできるの
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2022年12月27日
これの解説みたいなのを書きます。
この記事の参考文献にある “Bounds on the complexity of the longest common subsequence problem.” の冒頭で、できるとの記述があったので考えた結果です*1。
前提知識
まず、successor query という形式のクエリがあります。 管理している集合 $S \subseteq \N$ に対してクエリ $x$ が与えられ、「$S$ の要素で $x$ より大きいもののうち、最小のものは？」を答えるというものです*2。 存在しないときは $\infty$ としておきます。
たとえば、$S = \{2, 7, 61\}$ のとき、$x = 2$ や $x = 5$ に対しては $7$、$x = 61$ に対しては $\infty$ といった具合です。
集合への要素の追加・削除および successor query を $O(\log(n))$ 時間で処理できるデータ構造として、平衡二分木があるのは有名です。
競プロ界隈では比較的有名でないデータ構造*3として、vEB (van Emde Boas) tree や、y-fast trie というものがあります。 集合に入りうる最大値を $u$ として、以下のような計算量です。
| 名前 | 空間 | 時間 |
|---|---|---|
| vEB tree | $O(u)$ | $O(\log(\log(u)))$ |
| vEB tree (with hashing) | $O(n)$ | expected $O(\log(\log(u)))$ |
| y-fast trie | $O(n)$ | expected $O(\log(\log(u)))$ |
これらの紹介としては、下記の記事（にあるリンク）などがあります。
- cs166.1166/14 のスライド
- cs166.1166/15 のスライド
方針
LIS を求めるにあたって、セグ木で平面走査をする方針や、蟻本に載っている DP などが有名です。 ここでは後者をベースとした方針を用います。
たとえば [1, 4, 2, 3, 0] の LIS を求める際は、以下のような流れになります。
[oo, oo, oo, oo, oo] # 初め oo (= ∞) で初期化 ↓ [ 1, oo, oo, oo, oo] # 1 を入れて昇順になる位置に挿入 ↓ [ 1, 4, oo, oo, oo] # 4 について同様 ↓ [ 1, 2, oo, oo, oo] # 2 について同様 ↓ [ 1, 2, 3, oo, oo] # 3 について同様 ↓ [ 0, 2, 3, oo, oo] # 0 について同様 ↓ oo より左にある個数が LIS の長さとわかる
ここで、この配列の最終状態が実際の LIS になるとは限らないことには注意しましょう。
手法
さて、上記では配列で管理していた部分を、集合と見なすこともできます。
たとえば、[1, 4, oo, oo, oo] は $\{1, 4\}$ と見なします。
これに対して $2$ を入れるときは、$2$ の successor である $4$ を削除し、$2$ を集合に追加します。
これは、vEB tree などを用いることで、一つあたり $O(\log(\log(u)))$ 時間でできます。 順列なので $u = n-1$ であり、全体で $O(n\log(\log(n)))$ 時間です。
各要素が小さい方から何番目にあるかなどの管理は必要ありませんが、別途それが必要であれば管理は可能です。 追加しようとしている要素は既存の要素を上書きする（削除される要素以外の順位には影響しない）場合と、末尾に追加される場合しかないためです。
実装例
vEB バグってるかも。あんまりテストしてません。
その他
一般の整数列であれば、期待 $O(n \log(\log(u)))$ 時間とかでできそうです。 特に、$u = n^{O(\log(n))}$ であれば $O(n \log(\log(n)))$ ですね。
「vEB tree で処理できる形の解法を考えて $\log$ を $\log\circ\log$ にする」が好きな界隈、ありそうです。
おわり
にゃんこ。
