offline_dsp.html

<title>Decomposable searching problem - オフラインの場合</title>
<p>
この記事では<a href='http://yukicoder.me/wiki/decomposable_searching_problem'>前の記事</a>で紹介した分解可能問にオフラインで答える場合に使えるテクニックを紹介する。
「オンライン」「オフライン」の違いや、オンラインの場合のテクニックについては前の記事を参照のこと。
</p>
<h3 class='shadow'>ただのセグメント木</h3>
<p>
この記事で紹介することは「ただのセグメント木」である。
また、前の記事で紹介したテクニックもセグメント木を使っていると言える。セグメント木さえ知っていれば他に知識は必要ない。
以下に2種類の方法を説明する。
</p>
<h4 class='shadow'>クエリを区間として見る場合</h4>
<p>
元となる要素を追加された順に並べて考えると、クエリはその列に対する区間クエリである。
セグメント木の各ノードは、そのノード区間が含む要素に対し静的データ構造を構築する。
クエリはそのセグメント木に対して、そのクエリ区間の分割である区間のノードそれぞれの静的データ構造に対しクエリをしたものを組み合わせればよい。
</p>
<p>
要素の追加のみの場合、$t$個の要素が追加されたすぐ後に答えるクエリは$[1,t]$の区間に対応する。
もちろん、その他の任意の時間区間に対してのクエリ("time-windowed query")を行うことができる。
</p>
<p>
そのまま実装すると各データ構造が線形空間の場合でも$Θ(n \log n)$空間かかるが、セグメント木を深さ優先探索しながら必要のある部分だけ構築するなどすれば線形空間にすることができる。
</p>
<p>
前記事で紹介して「マージ」による高速化やフラクショナルカスケーディングも使える。
ただ、この場合"フラクショナル"カスケーディングは必要なく、"フルカスケーディング"と言えるもの(一般的な言葉ではない)でできる。
</p>
<h4 class='shadow'>要素を区間として見る場合</h4>
<p>
クエリを時間順に並べて考え、要素に対し「その要素を対象にするクエリ」という時間区間を割り当てる。
各要素の時間区間の分割に対応するセグメント木の各ノードに対しその要素を追加し、その追加された要素に対し静的データ構造を構築する。
クエリは、その時刻を含む各ノードに対し静的データ構造に対してクエリをしたものを組み合わせればよい。
</p>
<p>
要素の追加のみの場合、時刻$t$のクエリの直前に追加された要素は$[t,\infty)$の区間に対応する。最後のクエリが時刻$T$の場合は$[t,T]$とできる。
</p>
<p>
前記事で紹介した方法はこの「要素を区間として見る場合」である。ただし、最後のクエリの時刻というのはわからないため$[t,\infty)$に対応するが、
もちろん無限のノードは用意できないが、適切に考えると有限にできる。
</p>
<p>
この方法も適切にやれば空間計算量を削減できる。
フラクショナルカスケーディングも適用できるだろう。
また、一般には単純に「マージ」することはできないが、ソートをしたい場合には最初に全ての要素をソートしてその順に処理すれば各ノード内でソートする必要がなくなる。
</p>
<h5 class='shadow'>要素の削除</h5>
<p>
この方法は要素の削除に対応する。
時刻$t$のクエリの直前に追加され、時刻$u$のクエリの直後に削除された要素は$[t,u]$の区間に対応する。
この要素の削除に関して演算子の可逆性などは一切仮定していないことに注意しよう。これはオフラインの場合の優位な点である。
</p>
<h3 class='shadow'>さらにできること</h3>
<h4 class='shadow'>部分的なオンライン性</h4>
<p>
上記の2つの方法はどちらも要素の内容とクエリのタイミングがオフラインで与えられることは仮定しているが、クエリの内容は使っていない。
よって、全ての要素とその追加・削除のタイミングさえ最初に与えられれば、クエリの内容自体はオンラインで与えられても答えることができる。
</p>
<h4 class='shadow'>クエリもオフラインの場合</h4>
<p>
逆に、クエリの内容も全てオフラインで与えられる場合、できることが増えることがある。
今まで「静的データ構造」というものを仮定していたが、この場合はそれすら必要なく、「データとクエリ列が与えられたとき、全てのクエリに対しての答えを計算する」アルゴリズムさえあればよい。
</p>
<p>
たとえば、クエリがデータ上で二分探索をするという場合、最初にクエリもソートしておけばデータとクエリを「マージ」するだけで二分探索結果が得られる。
クエリのソートもデータのソートと同じくノードごとにやる必要はない。
つまり、フラクショナルカスケーディングなどのテクニックは必要なくなる。
</p>
<h4 class='shadow'>分解可能とは言えない場合でさえ - Batched Dynamic Connectivity</h4>
<p>
以下の問題を考える "dynamic connectivity"：
<ul>
<li>無向グラフを管理する。最初は辺が無い。
<li>辺の追加・削除の操作が与えられる。
<li>2つの頂点$u, v$が与えられ、「$u$と$v$は同じ連結成分に属するか？」というクエリに答える。
</ul>
この問題は、単純には分解可能問題とは言えない。
クエリの結果としてグラフを返し、演算子はそのグラフの和集合を取るという演算をすると考えれば分解可能と言えなくもないが、もちろんそのまま実装すると時間計算量は良くない。
それでもなお、この問題のオフラインバージョンは上で紹介したテクニックを用いて$O(m \log^2 m)$時間で解ける($m$はクエリ数)。
</p>
<p>
辺を要素とする。上で書いたように、要素を区間として見ればセグメント木のノードそれぞれに辺集合が割り当てられる。
トリックは、このセグメント木上をDFSすることである。
</p>
<p>
DFS中にUndo可能なUnion-findデータ構造を管理する。この実装に関してはここでは書かないが簡単に実装できる。
DFSにおいてセグメント木あるノードに到達した("in")とき、そのノードに割り当てられている全ての辺で"Union"操作を行う。
子ノードに再帰し、そのうち戻ってきて帰る("out")とき、"Undo"操作を行う。
これにより、常に現在のノードの祖先ノードに割り当てられている辺集合の和集合を管理していることになる。
葉ノードに到達した場合、その葉ノードに割り当てられているクエリは管理しているUnion-findデータ構造に対して行うことにより答えられる。
</p>
<p>
Union-findデータ構造の操作は$O(\log n)$($n$は頂点数。$n \in O(m)$と仮定できる)時間で実装でき、その操作回数は$O(m \log m)$回であるため、全体で$O(m \log^2 m)$時間となる。
</p>
<h5 class='shadow'>ちなみに</h5>
<p>
"dynamic connectivity"問題は、オンラインであってもならし$O(\log^2 m)$時間で解くことができる [1]。より高速な方法も提案されている [2]。
ただし、この記事のスコープ外であるためここでは説明しない。
</p>
<ul>
<li>[1] J Holm, K De Lichtenberg, M Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.</li>
<li>[2] M Thorup. Near-optimal fully-dynamic graph connectivity.</li>
</ul>
<h3 class='shadow'>演習問題</h3>
<ul>
<li><a href='http://codeforces.com/gym/100551/problem/A'>Dynamic connectivity contest A - Connect and Disconnect</a> - batched dynamic connectivity である。
<li><a href='http://codeforces.com/gym/100551/problem/D'>Dynamic connectivity contest D - Bridges: The Final Battle</a> - batched dynamic connectivity と同じようにできる。UnionFindの代わりにどのようなデータ構造を持てばいいか？
<li><a href='http://tkppc2.contest.atcoder.jp/tasks/tkppc2016_i'>技術室奥プログラミングコンテスト#2 I - ボス（Boss）</a> - 「要素を区間として見る」ことで削除に対応できる。もっとも、静的なバージョンを解くことが難しいのだが。
<li><a href='http://codeforces.com/contest/601/problem/E'>Codeforces Round 333 Div.1 E. A Museum Robbery</a> - クエリを時系列についてSegment Treeのように持つ。
</ul>
<p>(追加の問題例募集中)</p>