内容へ移動

現在位置: トップページ » アルゴリズム » データ構造 » Sparse Table

文書の表示

サイトマップ

差分

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

この比較画面へのリンク

--- programming_algorithm:data_structure:sparse_table [2019/12/05] – [±1-RmQ] ikatakos
+++ programming_algorithm:data_structure:sparse_table [2019/12/05] – [±1-RmQ] ikatakos
@@ 行 124: / 行 124: @@
 ブロック内の変化は、今回1ブロック3要素なので、%%「++」「+-」「-+」「--」%%の4通りしかない。
-ブロック内での、各パターンの区間  $[l, r]$  の最小値配列は、事前計算で作っておいても間に合う容量である。（ブロックサイズを  $s$  とすると  $s^22^{s-1}$ ）
+なので、全変化パターン・全区間  $[l, r]$  の最小値配列を事前計算で作っても、現実的な容量で間に合う。
+ブロックサイズを  $s$  とすると  $s^22^{s-1}$  の計算量とメモリがかかる。
+先頭要素が0だったとして、最小値を計算しておく。
   [++]           [+-]           [-+]           [--]
@@ 行 144: / 行 147: @@
  $\displaystyle \frac{\log_2{N}}{2}$  が良いとされている。端数はどちらでもよいが、とりあえず切り上げとする。
-というのも、こうするとブロックの個数は  $\displaystyle \frac{2N}{\log_2{N}}$  となる。
+こうするとSparseTable, 個別計算のいずれも事前計算とメモリが  $O(N)$  に収まる。
+SparseTableの方は、ブロックの個数が  $\displaystyle \frac{2N}{\log_2{N}}$  となる。
 この要素数でSparseTableを構築すると、 $\displaystyle \frac{2N}{\log{N}} \log {\frac{2N}{\log{N}}}=O(N)$  となる。
@@ 行 150: / 行 155: @@
 また、個別計算の方も、 $\displaystyle \frac{\log{N}}{2}^2 2^{\frac{\log{N}}{2}-1}=O(\log^2{N}\sqrt{N})$  となり、 $O(N)$  より小さくなる。

文書の表示

メディアマネージャー文書の先頭へ

CC Attribution 4.0 International