decomposable_searching_problem.html

<!--
  前から面白いテクニックだとは思っていたけどEducational Codeforces Roundで使う問題が出たのでこの際に書いてみた
  実装していないものに関してはいろいろと間違った記述をしている可能性がある。指摘してほしい。
-->
<title>Decomposable searching problem</title>
<p>
データに対するクエリをするという問題は多い。
例えば、数の集合を持ち存在判定クエリに答えるという問題や、数の組(a,b)の集合を持ち与えられたxに対してax+bの最大値を求めるという問題などが例として挙げられる。
</p>
<p>
クエリに答える問題は、データが「静的」な場合と「動的」な場合の2つに分けられる。
静的というのは全てのデータがはじめに与えられ、クエリはその変わらないデータに対するものということ。
動的というのはそうでなく、何らかのデータを変更する操作にも対応しなければならない。
</p>
<p>
ここではデータが要素の集合や列などで表されると仮定する。
その場合、データへの変更操作として「要素の追加」や「要素の削除」といったものが基本的なものとして考えられる。
クエリ問題のうち変更操作が「要素の追加」のみである場合、その問題を「インクリメンタル」であると呼び、「要素の削除」のみである場合「デクリメンタル」と呼ぶ。
この記事においては、順番の関係ある列に対する「要素の追加」は末尾に追加することを意味するとする。
</p>
<p>
クエリ問題の他の分類として「オンライン」と「オフライン(バッチ問題)」というものがあるが、ここではオンライン問題のみを考える。
オンラインというのは、クエリが与えられたらすぐにそのクエリに答えなければいけなく、たとえば次のクエリを読み込んでから前のクエリに答えるということはできないことを表す。
オフライン問題に対して使えるテクニックに関しては、<a href='https://yukicoder.me/wiki/offline_dsp'>次の記事</a>を参照のこと。
</p>
<p>
静的なクエリに答えるデータ構造があっても、動的なバージョンがうまく解けるとは限らない。
また、解けるとしてもデータ構造が複雑になることも多い。
静的なデータ構造を簡単に動的なデータ構造へ変換できる場合はどのような場合だろうか？ここでは、この質問の十分条件を示す。
</p>
<h3 class='shadow'>分解可能問題</h3>
<p>
データは要素の列で表されるとする。
クエリ問題が分解可能("decomposable searching problem"のここでの訳)であるとは、
<ul>
<li>要素1つだけのデータ$[e]$に対するクエリを$q([e])$と表すとき、
要素列に対するクエリは$q([e_1,e_2,\dotsc,e_n]) = q([e_1]) \star q([e_2]) \star \dotsb \star q([e_n])$となる演算子$\star$によって表すことができる。
<li>$\star$は結合法則を満たす。
</ul>
となるものをいう。
</p>
<p>
上で言及した問題はどれも分解可能である。
たとえば、「ax+bの最大値を求める」問題の場合$q_x([(a,b)]) = ax + b$, $\star = \max$と表すことができる。
</p>
<p>
"decomposable searching problem"という言葉とそれによる手法は[1]によって提案された。
</p>
<h3 class='shadow'>インクリメンタル costs only $\log n$</h3>
<p>
分解可能問題に対する静的なデータ構造が与えられたとき、これをインクリメンタルなデータ構造にすることができる。
その方法はある種のダブリングと言え、二項ヒープで使われているものと同じである。
</p>
<p>
インクリメンタルにしたデータ構造は元の静的なデータ構造を複数持つ。
データ列$a$に対する静的データ構造を$S(a)$と表すとすると、内部状態は$[S(a_1), \dotsb, S(a_k)]$として表すことができる。
また、各データ列$a_1, \dotsb, a_k$も全て持ち、データ列の長さ$|a_i|$も保持する。
</p>
<p>
初期状態は空$[]$である。
状態にデータ$e$を追加する場合、以下の処理を行う。
<ol>
<li>まず$S([e])$を構築し、状態の列に追加する。状態は$[S(a_1), \dotsb, S(a_{k-1}), S_k = S([e])]$となる。
<li>$k$をその時の状態列の長さとするとき、$k &gt; 1$であり$|a_{k-1}| = |a_k|$である限り、以下を繰り返す。
<ol>
<li>状態列から$S(a_{k-1})$と$S(a_k)$を削除する。
<li>$a_{k-1}$と$a_k$を連結し、新たな要素列を作る。これを$a'$と表す。
<li>$S(a')$を構築し、状態列に追加する。状態列は$[S(a_1), \dotsb, S(a_{k-2}), S(a')]$となる。
</ol>
</ol>
(必要な場合にのみ再構築することにより2倍程度高速化できる)
</p>
<p>
クエリに答えるには、各$S(a_i)$に対してクエリをして$\star$でまとめればよい。
</p>
<p>
このデータ構造によって管理される要素列の長さ$|a_i|$は2の累乗であることがわかる。
また、要素列の長さは常に降順になる。
つまり、要素の追加の処理は、同じサイズの静的データ構造がある限りそれらをマージし元の2倍の大きさのものにするということになる。
</p>
<p>
上記の操作の計算量を考えてみよう。$n$を要素の追加の回数とする。
それぞれの要素に対し、その要素を含む要素列に対する静的データ構造を構築する回数は$1 + \log_2 n$回以下である。
なぜなら、要素は常に1つの静的データ構造に含まれ、また、その要素を含む静的データ構造が破棄され作りなおされるとき、新たにその要素を含む要素列の長さは元の2倍となる。
要素列の長さは$n$を超えないため、$\log_2 n$回しか作りなおされることがないからである。
</p>
<p>
$n$要素の静的データ構造が$T(n)$時間で構築できる場合、$n$回の追加にかかる全体の計算量は$O(T(n) \log n)$時間となる。
つまり、1回の追加のならし計算量は$O(\frac{T(n)}{n} \log n)$となる。
また、$n$要素の静的データ構造に対するクエリと$\star$が$O(U(n))$時間で計算できるとき、インクリメンタルデータ構造に対するクエリは$O(U(n) \log n)$時間で可能となる。
($T(\cdot)$, $U(\cdot)$ に対する適切な仮定のもと)
</p>
<p>
上記の計算量はならし計算量であるが、最悪計算量を保証したい場合、一種の遅延評価によりそれが達成できる。
詳しくは参考文献[2]を参照。
</p>
<h4 class='shadow'>計算量が改善できる場合</h4>
<p>
上記のインクリメンタルデータ構造の時間計算量は、元となるデータ構造の性質によってさらに改善できることがある。
</p>
<p>
$S(a')$を構築するのに一から作り直すのではなく、$S(a_{k-1})$と$S(a_k)$に対して作られたデータ構造を"マージ"することにより計算量が改善できることがある。
たとえば、$S(a)$を構築するのに$a$のソートが必要な場合、そのソート済の列を持っておくことによりソートの$\Theta(n \log n)$時間をマージの$\Theta(n)$時間に改善できる。
</p>
<p>
クエリの計算量も改善できることがある。
クエリが、与えられた値に対する何らかの二分探索が必要だという場合、<a href='https://en.wikipedia.org/wiki/Fractional_cascading'>Fractional cascading</a> [3]を用いることにより、
$\Theta(\log n)$個のデータ構造に対して合計$\Theta(\log^2 n)$時間をかけて個別に二分探索をする必要がなくなり、合計$\Theta(\log n)$時間に改善できる。
</p>
<h4 class='shadow'>削除 - $\star$が可換かつ可逆な場合</h4>
<p>
$\star$が可換かつ可逆である場合、削除に対応できる。
たとえば、整数の足し算$+$はこの条件を満たすため、「ある条件に一致する要素の数を数える」というようなクエリの場合は削除に対応できる。
追加用と削除用の2つのインクリメンタルデータ構造を持つ。
要素の追加は追加用データ構造に追加する。要素の削除は削除用のデータ構造に追加する。
クエリに答えるには、追加用のデータ構造に対するクエリ結果から削除用のデータ構造に対するクエリ結果を引けばよい。
あるいは、静的なデータ構造が要素の"重み"に対応する場合、重み$w$の要素の削除を重み$-w$の要素の削除と変換して追加することでも対応できる。
</p>
<p>
"削除"は実際には要素の削除をしないため計算量にでてくる$n$が本来の要素数より大きくなることがあるが、ほとんどの場合問題ないだろう。
もし$n$を実際の要素数に対応させたい場合、削除された要素が定数割合を超えたら全て構築しなおす(global rebuilding)という基本的なテクニックにより対応できる。
</p>
<h4 class='shadow'>削除 - スタックとして</h4>
<p>
※筆者は実装していないので、この節の文章は間違っている可能性があります。
</p>
<p>
最悪計算量を保証するバージョンを使えば、スタックの操作をすることができると思われる。つまり、FIFOの削除ができる。
また、スタックを使えばキューやデックを実装することができるため、それらの操作もできると思われる。
</p>
<h4 class='shadow'>削除 - semi-online</h4>
<p>
挿入の際に削除時刻が指定される"semi-online"の場合も効率的に解くことができる[4]。
</p>

<h3 class='shadow'>問題例</h3>
<h4>「ax+bの最大値を求める」問題</h4>
<p>
静的なバージョンは"convex-hull trick"と呼ばれるデータ構造により解くことができる。
これは平衡二分探索木により直接的にインクリメンタルにすることもできるが、分解可能問題として上記の手法を適用することもできる。
</p>
<p>
静的データ構造は最初にソートを必要するが、その他は線形時間である。
上記のようにソートのかわりにマージをすることにより、点の追加をならし$O(\log n)$時間で行うことができる。
これは直接的に動的にした場合と同じ計算量であるが、配列やスタックといった基本的なデータ構造のみで実装できるという利点がある。
</p>
<h4 class='shadow'>優先度付きキュー</h4>
<p>
優先度付きキューをこの手法を用いて実装することができる。
実際には、最小値と最大値の両方を取得・削除できる両端優先度付きキューが実装できる。
各要素列はソートされた状態で持つ。
最小値・最大値の削除に対応するため、それに加え「どこまで削除されたか」という両端のインデックスを各要素列に対して持つ。
要素の追加はマージをすることでならし$O(\log n)$時間で実装できる。このとき、すでに削除された要素は適切に扱う。
最小値・最大値の削除は「どこまで削除されたか」を変更するだけで済む。クエリも$O(\log n)$時間となる。
この優先度付きキューの良い特徴としては、メモリを$n + O(\log n)$ワードしか使わないという点である(ただし$n$には削除された要素も含む)。
さらに、「同じ優先度の要素は追加された時間通りの順番で扱う」という特徴も追加のメモリを使用することなく実装できる。これは二分ヒープなどで追加のメモリを使用することなく実装するのは難しい。
</p>
<h3 class='shadow'>演習問題</h3>
<ul>
<li>両端優先度付きキューの実装
<ol>
<li>紹介した両端優先度付きキューを実装せよ。ただし、メモリ使用量は気にしなくてもよい。二分ヒープと実行時間を比較せよ。
<li>上で紹介した"fractional cascading"を実装し、最小値・最大値の削除がならし$O(\log n)$時間でできるように変更せよ。
<li>遅延評価により最悪計算量が$O(\log n)$時間になるように変更せよ。実行時間はどう変化するか？
<li>スタック、キュー、デックの操作を実装せよ。または筆者に間違い指摘せよ(間違っている場合)。
</ol>
<li>以下の問題を紹介したテクニックを用いて解いてみよ(追加の問題例募集)。
<ul>
<li><a href='http://codeforces.com/contest/710/problem/F'>Educational Codeforces Round 16 F - String Set Queries</a> - 静的なバージョンはAho-Corasickアルゴリズムにより解くことができる。
<li><a href='https://codevillage.sdslabs.co/competitions/insomnia16/problems/INS16C'>Insomnia 2016 C - Maximum Toll</a> - incremental convex hull trick (をさらに適当なテクニックと組み合わせる)
<li><a href='https://www.codechef.com/OCT15/problems/JUMP'>October Challenge 2015 - Jump mission</a> - incremental convex hull trick (をさらに適当なデータ構造に載せる)
<li><a href='https://atcoder.jp/contests/abc244/tasks/abc244_h'>AtCoder Beginner Contest 244 Ex - Linear Maximization</a> - incremental convex hull
</ul>
<li>上の"String Set Queries"を少し変更した問題を考えよう。
文字列の集合$S$を追加・削除に対して管理するが、文字列$t$が与えられたクエリで$\sum_{s \in S} {\rm occur}(s, t)$を答えたい。
ここで、${\rm occur}(s, t)$とは、$s$中に$t$が部分文字列として出現する位置の個数を表す(元の問題は$\sum_{s \in S} {\rm occur}(t, s)$であった)。
どのような計算量で解けるか？
<li>[1]では「Nearest neighbor」問題が紹介されている。静的なバージョンはボロノイ図を使うデータ構造により解くことができる。このインクリメンタルバージョンを実装してみよ。
<li>メタ：このテクニックを使う面白い問題を出題してみよ。
</ul>
<h3 class='shadow'>参考文献</h3>
<ul>
<li>[1] JL Bentley, JB Saxe. Decomposable searching problems.
<li>[2] MH Overmars, J van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems.
<li>[3] B Chazelle, LJ Guibas. Fractional cascading.
<li>[4] D Dobkin, S Suri. Maintenance of geometric extrema.
</ul>