差分

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

--- programming_algorithm:data_structure:sparse_table [2019/12/04] – [実装] ikatakos
+++ programming_algorithm:data_structure:sparse_table [2019/12/05] – [±1-RmQ] ikatakos
@@ 行 49: / 行 49: @@
 ===== 実装 =====
-PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。
+以下の条件を満たす場合、PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。
-（ただしminimum, maximumなど要素同士の演算を行う関数がNumPyに用意されているものに限る）
+  * minimum, maximum, lcm, gcdなど2つの配列の要素同士の演算を行う関数がNumPyに用意されている
+  * 最小値の値そのものがわかればよく、最小値のindexは復元できなくてもよい
+（※未バリデーション）
 <sxh python>
@@ 行 72: / 行 76: @@
     def query(self, l, r):
-        """ [l, r) """
+        """ min value of [l, r) """
         d = r - l
         if d == 1:
@@ 行 82: / 行 86: @@
 </sxh>
+===== バリエーション =====
+==== ±1-RmQ ====
+$A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の最小値/最大値を求める場合。
+この場合、実装はちょっとややこしくなるが、クエリ応答は $O(1)$ のまま、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。
+なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。
+（とはいえ競プロの文脈では、logのあるなしだけでTLEになるケースは稀で、実装の手間からこちらを選ぶのはよほどあとちょっとで通らない場合に限られる）
+  * [[https://www.slideshare.net/yumainoue965/lca-and-rmq|LCA and RMQ ~簡潔もあるよ！~]]
+  * [[http://joisino.hatenablog.com/entry/2017/08/13/210000|前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ]]
+概要は、SparseTableと、平方分割などに代表されるようなブロック分割の合わせ技。
+  * "ちょうどいいサイズ"のブロックに分割して、ブロック単位で最小値を求めておく
+  * ブロックを1要素として、SparseTableを構築する
+  * クエリに対して、完全に覆われるブロック内の最小値はSparseTableで求められる
+  * はみ出る部分は個別に計算するが、変化パターンが限られるので、事前計算して持っておいても大したサイズにならない
+   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 |
+        |         |         |         |          |          |          |          |          |          |          |
+  Ai    | 5  4  3 | 4  5  6 | 5  6  7 |  6  7  8 |  9  8  7 |  6  5  4 |  3  2  3 |  2  1  2 |  3  2  3 |  4  5  6 |
+        |         |         |         |          |          |          |          |          |          |          |
+  Min   |       3 | 4       | 5       |  6       |        7 |        4 |     2    |     1    |     2    |  4       |
+  Query                            |----------------------------------------------------------------|
+  ここはSparseTableで計算             |------------------------------------------------------|
+  ここは個別に計算                 |-|                                                        |-----|
+== 個別に計算 ==
+ブロック内の変化は、今回1ブロック3要素なので、%%「++」「+-」「-+」「--」%%の4通りしかない。
+なので、全変化パターン・全区間 $[l, r]$ の最小値配列を事前計算で作っても、現実的な容量で間に合う。
+ブロックサイズを $s$ とすると $s^22^{s-1}$ の計算量とメモリがかかる。
+先頭要素が0だったとして、最小値を計算しておく。
+  [++]           [+-]           [-+]           [--]
+  l\r 0  1  2    l\r 0  1  2    l\r 0  1  2    l\r 0  1  2
+  0  0  0     0  0  0  0     0  0 -1 -1     0  0 -1 -2
+     1  1     1     1  0     1    -1 -1     1    -1 -2
+        2     2        0     2        0     2       -2
+例えば上の例で $i=7,8,9$ のブロックは「%%++%%」パターンであり、はみ出ている区間は $[2, 2]$ なので、テーブルを参照すると 2 である。
+ブロックの先頭要素 5 に 2 を足して、7 が区間の最小値とわかる。
+また、$i=25,26,27$ のブロックは「%%-+%%」パターンであり、区間 $[0, 1]$ のテーブル参照は-1である。
+ブロックの先頭要素 3 に -1 を足して、2 が区間の最小値である。
+== ブロックサイズ ==
+大きくしすぎると個別計算の計算量・メモリが増え、小さくしすぎるとSparseTableの計算量・メモリが増える。
+$\displaystyle \frac{\log_2{N}}{2}$ が良いとされている。端数はどちらでもよいが、とりあえず切り上げとする。
+こうするとSparseTable, 個別計算のいずれも事前計算とメモリが $O(N)$ に収まる。
+SparseTableの方は、ブロックの個数が $\displaystyle \frac{2N}{\log_2{N}}$ となる。
+この要素数でSparseTableを構築すると、$\displaystyle \frac{2N}{\log{N}} \log {\frac{2N}{\log{N}}}=O(N)$ となる。
+（ちゃんとは理解してないけど、式変形すると $\displaystyle 2N(\log_N{2N}-\log_N{\log{N}})$ となり、対数の部分は極限取るとすぐ1になるので無視できる）
+また、個別計算の方も、$\displaystyle \frac{\log{N}}{2}^2 2^{\frac{\log{N}}{2}-1}=O(\log^2{N}\sqrt{N})$ となり、$O(N)$ より小さくなる。