$N$ 個の数区間 $R_i = [F_i,T_i) $ が与えられる。それに加え、クエリが $Q$ 個飛んでくる。それぞれついて答えよ。
- 数区間 $ [A_j, B_j ) $が与えられる。$R$ のうち、$ [A_j, B_j ) $ に含まれるものはいくつあるか。
制約
- $ 1 \leq N \leq 10^{5} $
- $ 1 \leq F_i \lt T_i \leq 10^{5} $
- $ 1 \leq Q \leq 10^{5} $
- $ 1 \leq A_j \lt B_j \leq 10^{5} $
以降、カウント対象の数区間 $[F_j, T_j)$ のことを 対象区間、クエリで与えられる区間 $[A_j, B_j)$ のことを クエリ区間 と呼ぶ。
ちなみに、この問題が解けると 数列の区間中の種類数を求めるクエリ にも答えることができる。（以下の記事の解法3を参照。）
解法1 : 平面走査
対象区間、およびクエリ区間をあわせて、終了位置でソート。それぞれの区間について、左から順番に処理すると解ける。 具体的には、以下のようにする。
- 点更新、区間加算ができるデータ構造を用意する。(ex: セグメント木、BIT
- 両区間を終了位置でソート。
- 対象区間の終了位置に出会った
- その開始位置に対して +1 する
- クエリ区間の終了位置に出会った
- この時点でクエリ区間中の +1 の合計が答えになる。
例えば、R = [1, 3), [5, 8), [6, 7), Q = [2, 7), [4, 9) の場合は・・・
まずこれらを終了位置の昇順にソート。（この問題の場合、終了位置が同じ場合はクエリ区間の方を後に置くように注意。）
- 対象区間
[1, 3)を処理。1の位置に +1。 - 対象区間
[6, 7)。6の位置に +1。 - クエリ区間
[2, 7)。今のデータ構造の[2, 7)の合計を答える。(下図) - 対象区間
[5, 8)。5の位置に +1。 - クエリ区間
[4, 9)。今のデータ構造の[4, 9)の合計を答える。
計算量は事前のソート処理で、$O( (N+Q)log(N+Q) )$ となる。実装例は以下。
さて、この解法はクエリの内容を先読みする、というものであった。つまり オフラインアルゴリズムである。 これを計算量をキープしつつオンラインにする方法を2つ紹介する。
解法2 : 平面走査・永続版
解法1で用いたデータ構造を永続化することにより、クエリにオンラインで答えることができる。 この問題の場合では、平面走査のときにやった 対象区間の開始位置に対して +1 する 操作の履歴データを持つ。 クエリに答えるときは、 そのクエリ区間の終了位置まで +1 をしたデータ構造 を履歴から取り出し、それに対して区間クエリを実行、答えを得る。
R = [1, 3), [5, 8), [6, 7), Q = [2, 7), [4, 9) の場合を図示する。
オフラインならば上図の赤いタイミングでクエリを処理できたが、今回は位置が分からないので・・・
このように、それぞれの対象区間を処理したタイミングでのデータ構造を持っておけば、後でどこにクエリが来ても正しく答えが出る。例えば、下図において [2, 7) のクエリを処理する際は「データ構造2」における区間 [2, 7) の合計を、[4, 9) のクエリは 「データ構造3」の [4, 9) の合計を答えればよい。
普通に情報をすべて持つと、データ構造の操作回数を $α$ として $O(αN)$ のメモリが必要になるが、 必要な部分を使いまわすことで追加のメモリが $O(αlogN)$ に抑えられる。また、一度の操作で必要になる計算量も $O(logN)$ である。
オフライン解に比べてメモリが余分に $O(NlogN)$ 必要だが、時間計算量は事前準備・クエリの処理を合わせて $O( (N+Q)logN )$ である。
解法3 : Wavelet tree
解法1, 解法2とは別のアプローチを紹介する。 対象区間の開始位置を横軸、終了位置を縦軸にとってプロットすると、各クエリは以下の図のように、長方形に含まれる点の数をカウントする問題になる。
長方形内の点のカウントには、Wavelet treeが使える。Wavelet treeについては ウェーブレット木の世界 が詳しい（本エントリでは扱わない）。簡単に説明すると、列データを順序を保ちつつその値の大小で左右に分割するような二分木になっている。一度構築すれば、区間に対する様々な操作が行える。例えば、
- 区間内でK番目に小さい値
- 区間内の指定範囲値のカウント
などが $O(logM)$ (M:= 値の最大値、座標圧縮すれば要素数に) で求まる。
この問題の場合、例えばデータ列のインデックスに開始位置（ただし、これらがユニークな値になるように適当に番号を振る必要がある）を持ち、値に終了位置を持つようにすれば 各クエリが指定範囲値のカウント問題に帰着できる。当然これらの処理はオンラインで可能。*1
謝辞
色々教えていただいたのでこの記事を生やすことができました。ありがとうございます。
https://twitter.com/maroon_kuri/status/854898429603962880
segtreeに対し、はじめに与えられた区間をline sweepで追加するけど、その追加した任意の時点のsegtreeを取り出せるのが永続segtree
— 有為 (@uwitenpen) 2017年4月21日
2次元平面に点がN個あって、長方形の中に点が何個あるか？、というクエリはwavelet treeを使うとO(logN)だったと思います
— よすぽ (@yosupot) 2017年4月20日
*1:各クエリで範囲を指定するときの端の処理に注意。
