差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:sparse_table [2019/12/05] – [実装] ikatakos | programming_algorithm:data_structure:sparse_table [2019/12/05] – ikatakos | ||
---|---|---|---|
行 49: | 行 49: | ||
===== 実装 ===== | ===== 実装 ===== | ||
- | PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。 | + | 以下の条件を満たす場合、PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。 |
- | (ただしminimum, maximum, lcm, gcdなど2つの配列の要素同士の演算を行う関数がNumPyに用意されているものに限る) | + | |
+ | * minimum, maximum, lcm, gcdなど2つの配列の要素同士の演算を行う関数がNumPyに用意されている | ||
+ | * 最小値の値そのものがわかればよく、最小値のindexは復元できなくてもよい | ||
+ | |||
+ | (※未バリデーション) | ||
<sxh python> | <sxh python> | ||
行 82: | 行 86: | ||
</ | </ | ||
+ | |||
+ | |||
+ | ===== バリエーション ===== | ||
+ | |||
+ | ==== ±1-RmQ ==== | ||
+ | |||
+ | $A=\{A_0, | ||
+ | |||
+ | この場合、実装はちょっとややこしくなるが、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。 | ||
+ | |||
+ | なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。 | ||
+ | |||
+ | (とはいえ競プロの文脈では、logのあるなしだけでTLEになるケースは稀で、実装の手間からこちらを選ぶのはよほどあとちょっとで通らない場合に限られる) | ||
+ | |||
+ | * [[https:// | ||
+ | * [[http:// | ||
+ | |||
+ | 概要は、SparseTableと、平方分割などに代表されるようなブロック分割の合わせ技。 | ||
+ | |||
+ | * " | ||
+ | * ブロックを1要素として、SparseTableを構築する | ||
+ | * クエリに対して、完全に覆われるブロック内の最小値はSparseTableで求められる | ||
+ | * はみ出る部分は個別に計算するが、変化パターンが+1か-1のみなので、どのパターンが事前計算して持っておいても大したサイズにならない | ||
+ | |||
+ | | ||
+ | | | ||
+ | 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 | ||
+ | | ||
+ | Query |----------------------------------------------------------------| | ||
+ | ここはSparseTableで計算 | ||
+ | ここは個別に計算 | ||
+ | |||
+ | == 個別に計算 == | ||
+ | |||
+ | ブロック内の変化は、今回1ブロック3要素なので、%%「++」「+-」「-+」「--」%%の4通りしかない。 | ||
+ | |||
+ | ブロック内での、各パターンの区間 $[l, r]$ の最小値配列は、事前計算で作っておいても間に合う容量である。(ブロックサイズを $s$ とすると $s^22^{s-1}$) | ||
+ | |||
+ | [++] | ||
+ | l\r 0 1 2 l\r 0 1 2 l\r 0 1 2 l\r 0 1 2 | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | 例えば上の例で $i=7,8,9$ のブロックは「%%++%%」パターンであり、はみ出ている区間は $[2, 2]$ なので、テーブルを参照すると 2 である。 | ||
+ | ブロックの先頭要素 5 に 2 を足して、7 が区間の最小値とわかる。 | ||
+ | |||
+ | また、$i=25, | ||
+ | ブロックの先頭要素 3 に -1 を足して、2 が区間の最小値である。 | ||
+ | |||
+ | == ブロックサイズ == | ||
+ | |||
+ | 大きくしすぎると個別計算の計算量・メモリが増え、小さくしすぎるとSparseTableの計算量・メモリが増える。 | ||
+ | |||
+ | $\displaystyle \frac{\log_2{N}}{2}$ が良いとされている。端数はどちらでもよいが、とりあえず切り上げとする。 | ||
+ | |||
+ | というのも、こうするとブロックの個数は $\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)$ より小さくなる。 | ||
+ | |||