静的データ構造で動的に処理する (1)

検索クエリを処理する前に，要素の変更に関するクエリを処理をし終えている必要があるようなデータ構造を静的データ構造と呼びます． そうではなくて，検索クエリと変更クエリが入り混じっていても処理できるようなデータ構造を動的データ構造と呼びます．

問題設定

ある集合*1 \(T\) の要素に関する以下の二種類のクエリを処理をする問題を考えます．

• データ構造に \(t\in T\) を追加する
• 何かしらの検索クエリに答える

直接これを処理する動的データ構造を持っていればそれをぺたりして終了なんですが，今回はこのクエリに関する静的データ構造しか持っていない状況を考えます．

要素 \(t_l, \dots, t_r\) を追加したあとの静的データ構造 \(d\) を \(d[t_l, \dots, t_r]\) と書くことにします． \(d[t_1, \dots, t_p, \dots, t_q]\) に対する検索クエリの答えを，\(d[t_1, \dots, t_p]\) と \(d[t_{p+1}, \dots, t_q]\) それぞれに対する検索クエリの答えから復元できるとき，\(d\) を用いて動的に処理することができます．すなわち，任意の順での追加と検索に対応できます．

方法

静的データ構造の（可変長）配列 \(D\) を用意します． \(D_i\) が管理している \(T\) の要素を直接持っておく配列 \(A_i\) も必要に応じて持っておきます．

追加クエリ

\(t\) を追加することを考えます． 一時的な \(T\) の配列 \(a\) を用意し，\(a = (t)\) としておきます．

1. \(i = 0\) で初期化します．
2. \(A_i\) が空なら，\(A_i \gets a\) とし，\(A_i\) の要素からなる静的データ構造を構築し，これを \(D_i\) として終了します．
3. そうでないなら，\(a\) の末尾に \(A_i\) の各要素を挿入し，\(A_i\) および \(D_i\) を破棄します．
4. \(i \gets i + 1\) とし，2. に戻ります．

検索クエリ

\(D\) の要素を \(d_0, \dots, d_{m -1}\) とし，\(d_i\) に関するクエリの答えを \(q_i\) とします． このとき，求めるべき答えは \(q_{m -1}, \dots, q_0\) から復元できます． 復元の方法が可換であれば添字の昇順で求めてもいいと思います．

計算量解析

\(A\) に入っている要素の個数の合計を \(n\) とします． このとき，\(A_i\) の要素数は次のように言えます．

• \(n\) の下から \(i\) bit 目が 0 なら \(0\)
• \(n\) の下から \(i\) bit 目が 1 なら \(2^i\)

追加の方法から，\(D_i\) が構築されるのは（繰り上がりによって）\(n\) の \(i\) 番目のビットが 1 のタイミングです． \(0\) から \(2^m -1\) まで数える間に \(i\) 番目の bit が 0 から 1 になるのは \(2^m / 2^{i+1} = 2^{m-i-1}\) 回程度ですので，\(D_i\) が構築されるのも \(2^{m-i-1}\) 回程度になります．

ここで，\(d[t_1, \dots, t_k]\) の構築にかかる時間を \(O(f(k))\) とします． このとき，\(D_i\) の構築一回にかかる時間は \(O(f(2^i))\) ですので，全体を通して \(D_i\) の構築にかかる時間の合計は \(O(f(2^i)) \times 2^{m-i-1}\) です．

\(f(k) = O(k)\) だとうれしいので，そういうことにすると，これは \(O(2^{m -1})\) となります． \(D\) の要素数が最終的に \(n\) 個になるとすると，\(D\) の要素数は \(\lceil\log_2 n\rceil\) です． 上でいう \(m\) は \(\log_2 n\) 程度ですので，全体にかかる時間は \(O(n\log n)\) です．

検索クエリも，元々の検索クエリにかかる時間の \(\log_2 n\) 倍程度の時間で処理できます．

注意：\(T\) が文字列の場合など，\(f(k)\) が要素によって変わる場合はまた別の解析が必要になりそうです．

応用

削除クエリに対応したいときはどうしましょう．

集合 \(S\) における \(x\) の出現数を数える問題などでは，\(S\) に関するデータ構造と \(S\) から削除された要素を管理するデータ構造を用意し，各々に対して出現数を数えて引き算すればいいですね．

そうじゃない状況についてはもっと考える必要がありそうです．今のえびちゃんにはまだ難しいです．

問題の例

Codeforces Educational Round 16 F – String Set Queries

codeforces.com

Aho–Corasick 法によるパターンマッチオートマトンは静的データ構造ですが，今回の方法を用いて動的に処理することができます．

提出コード

当然みたいに Aho–Corasick 法を知っているみたいな前提で書いてしまったんですが，知らない人はお勉強してください． えびちゃんは これ を見ながら勉強しました．

おわり

にゃんこ

*1:型と呼んだ方が伝わる？