差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:sparse_table [2019/12/05] – [±1-RmQ] ikatakos
+++ programming_algorithm:data_structure:sparse_table [2023/10/13] (現在) – ikatakos
@@ 行 2: / 行 2: @@
   * [[http://tookunn.hatenablog.com/entry/2016/07/13/211148|Sparse Tableを知ったので、忘れないように。 - tookunn’s diary]]
+<note>2022/07/15 ブロック分割の項目を追加</note>
 ===== 概要 =====
@@ 行 13: / 行 15: @@
   * 更新はできない
-足し算は冪等性を満たさないため、使えない。
+足し算は冪等性を満たさないため、使えない。\\
-（別に使ってもいいのだが、クエリ処理に計算量 $O(\log{N})$ かかるようになるし、
+データの持たせ方を工夫した DisjointSparseTable なら可能。（ただ、そもそも足し算なら累積和で区間クエリには答えられる）
-それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない）
+  * [[programming_algorithm:data_structure:sparse_table:disjoint_sparse_table]]
+min, maxの他には、最小公倍数/最大公約数、bitwise-and/or なども冪等性を満たす。
-min, maxの他には、最小公倍数/最大公約数なども冪等性を満たす。
 ===== データ構造 =====
@@ 行 34: / 行 38: @@
   |----------|                   3
   |----------------------|       1
+  i=1
+      j=0     |-|                         6
+     |----|                      3
+     |----------|                3
+     |----------------------|    1
+  ...
 これを計算しておくと、例えば $[2,8)$ の最小値は、以下のように求められる。
@@ 行 89: / 行 99: @@
 ===== バリエーション =====
+==== ブロック分割 ====
+$A_0,...,A_{N-1}$ をあらかじめ $B$ 個ごとのブロックに分け、ブロックに対しSparse Tableを構築する手法。
+=== 活用シーン ===
+主に以下の場合などに使われうる。
+  * 「$[l,r)$ の結果に $A_r$ を追加する」（区間を1伸ばす）計算量が、「$[l_1,r_1)$ と $[l_2,r_2)$ の結果同士をマージする」計算量より小さい
+  * 数列長 $N$ に比べ、クエリ数 $Q$ が小さい
+  * 通常のSparse Tableで $O(N \log{N})$ 個の情報を保存しておくにはメモリが足りない
+特に1つめが成り立つときに効果が大きいが、単純なSparse Tableに比べ処理が煩雑になり、
+その分、定数倍もかさむので、劇的に改善することは期待しない方がよいかも。使いどころが難しい。
+=== 概要 ===
+「クエリ区間に完全に包括されるブロック区間」についてSparse Tableの前計算結果を利用し、はみ出た分は愚直に計算する。
+   i    0  1 ... B-1 | B ... 2B-1 | 2B ... | 3B ... | 4B ... | 5B ... | 6B ... |
+  クエリ         |----------------------------------------------------------|
+  愚直に計算     |---|
+  table[1][2]        |---------------------------------------|
+  table[2][2]                     |-----------------------------------|
+  愚直に計算                                                          |-----|
+  以上をマージしてクエリの答えとする
+=== 計算量 ===
+例えば求めたい演算処理が、「区間を1つだけ広げる計算量は $O(x)$ だが、
+結果のマージには $O(y)$（$x \lt y$）かかるような性質」を持っていると、
+  * 全てをSparse Table化する場合
+    * 事前計算 $O(N y \log{N})$
+    * $Q$ 回のクエリ $O(Qy)$
+  * ブロック分割する場合
+    * 事前計算 $O(Nx+\dfrac{N}{B}y\log{\dfrac{N}{B}})$
+    * $Q$ 回のクエリ $O(Q(Bx+y))$
+クエリあたりの計算量を犠牲に、事前計算の計算量・メモリを減らすことができる。
+事前計算とクエリのバランスを取るブロック長 $B$ はなかなか綺麗な形にはならないが、
+いろいろ端折って計算すると $B=\sqrt{\dfrac{Ny\log{N}}{Qx}}$ を目安に設定すればよさそう。
+その場合、全体で $O(Nx+\sqrt{NQxy\log{N}}+Qy)$ となり、
+$x \lt y, N \ge Q$ の場合に、全てをSparse Table化するより高速になることがわかる。
 ==== ±1-RmQ ====
-$A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の最小値/最大値を求める場合。
+上記のブロック分割の考え方にさらに制約を課して、省メモリ化・高速化する手法。
-この場合、実装はちょっとややこしくなるが、クエリ応答は $O(1)$ のまま、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。
+=== 概要 ===
+$A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、
+必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の場合、
+その区間最小値や最大値は、クエリ応答は $O(1)$ のまま、
+事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。\\
+（結果のマージは $O(1)$ とする）
 なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。
@@ 行 103: / 行 171: @@
   * [[http://joisino.hatenablog.com/entry/2017/08/13/210000|前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ]]
-概要は、SparseTableと、平方分割などに代表されるようなブロック分割の合わせ技。
+ブロック分割をベースの考え方として、
+「はみ出た部分」の計算をクエリ毎に愚直に行うのではなく、
-  * "ちょうどいいサイズ"のブロックに分割して、ブロック単位で最小値を求めておく
+変化パターンが限られるのでパターン毎に事前計算しておくという発想。
-  * ブロックを1要素として、SparseTableを構築する
-  * クエリに対して、完全に覆われるブロック内の最小値はSparseTableで求められる
-  * はみ出る部分は個別に計算するが、変化パターンが限られるので、事前計算して持っておいても大したサイズにならない
+  B=3
    i    | 1  2  3 | 4  5  6 | 7  8  9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21 | 22 23 24 | 25 26 27 | 28 29 30 |
         |         |         |         |          |          |          |          |          |          |          |
@@ 行 124: / 行 191: @@
 ブロック内の変化は、今回1ブロック3要素なので、%%「++」「+-」「-+」「--」%%の4通りしかない。
-なので、全変化パターン・全区間 $[l, r]$ の最小値配列を事前計算で作っても、現実的な容量で間に合う。
+なので、全変化パターン・ブロック内の相対位置による区間 $[l, r]$ ごとに、
-ブロックサイズを $s$ とすると $s^22^{s-1}$ の計算量とメモリがかかる。
+最小値の左端要素からの差分配列を作っても、現実的な容量で間に合う。
-先頭要素が0だったとして、最小値を計算しておく。
+ブロックサイズを $B$ とすると $B^22^{B-1}$ の計算量とメモリがかかる。
+  先頭要素が0だったとして、変化パターン毎に最小値を計算
   [++]           [+-]           [-+]           [--]
   l\r 0  1  2    l\r 0  1  2    l\r 0  1  2    l\r 0  1  2
@@ 行 135: / 行 204: @@
         2     2        0     2        0     2       -2
-例えば上の例で $i=7,8,9$ のブロックは「%%++%%」パターンであり、はみ出ている区間は $[2, 2]$ なので、テーブルを参照すると 2 である。
+例えば上の例で $i=7,8,9$ のブロックは「%%++%%」パターンであり、はみ出ている区間は $[9, 9]$、
-ブロックの先頭要素 5 に 2 を足して、7 が区間の最小値とわかる。
+ブロック内の相対的な位置になおすと $[2,2]$ なので、
+「%%++%% テーブル」から $l=2,r=2$ を参照すると $2$ である。
+ブロックの先頭要素 $5$ に $2$ を足して、$7$ が区間の最小値とわかる。
-また、$i=25,26,27$ のブロックは「%%-+%%」パターンであり、区間 $[0, 1]$ のテーブル参照は-1である。
+また、$i=25,26,27$ のブロックは「%%-+%%」パターンであり、区間 $[0, 1]$ のテーブル参照は $-1$ である。
-ブロックの先頭要素 3 に -1 を足して、2 が区間の最小値である。
+ブロックの先頭要素 $3$ に $-1$ を足して、$2$ が区間の最小値である。
-== ブロックサイズ ==
+=== 計算量 ===
-大きくしすぎると個別計算の計算量・メモリが増え、小さくしすぎるとSparseTableの計算量・メモリが増える。
+ブロックサイズを大きくしすぎると個別計算の計算量・メモリが増え、小さくしすぎるとSparseTableの計算量・メモリが増える。
-$\displaystyle \frac{\log_2{N}}{2}$ が良いとされている。端数はどちらでもよいが、とりあえず切り上げとする。
+$\displaystyle \frac{\log_2{N}}{2}$ が良いとされている。
 こうするとSparseTable, 個別計算のいずれも事前計算とメモリが $O(N)$ に収まる。
@@ 行 158: / 行 229: @@
 === 拡張性 ===
-必ずしも±1で遷移する場合に限定しなくても、ブロック内全区間の事前計算テーブルのパターン数が $2^s$ 程度で収まる場合、同じ理由で活用できそう。具体的にあるかは知らんけど。
+必ずしも±1で遷移する場合に限定しなくても、ブロック内の変化パターン数が $2^B$ 程度で収まる場合、同じ理由で活用できそう。具体的にあるかは知らんけど。