Sparse Table

• Sparse Tableを知ったので、忘れないように。 - tookunn’s diary

• 区間最小値/最大値など、区間に対するクエリに答えられる
• 演算 $\oplus$ は、以下の条件を満たす必要がある（min, maxに相当するもの）
  • 結合則: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
  • 冪等性: $A \oplus A = A$
• クエリ処理はとても速い $O(1)$
• 事前計算の計算量・メモリは少し多めに必要になる $O(N \log{N})$
• 更新はできない

足し算は冪等性を満たさないため、使えない。 （別に使ってもいいのだが、クエリ処理に計算量 $O(\log{N})$ かかるようになるし、 それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない）

min, maxの他には、最小公倍数/最大公約数なども冪等性を満たす。

数列 $A=\{A_0,A_1,A_2,...,A_{N-1}\}$ の区間最小値を求めるとする。

以下の事前計算を行う。

$table[i][j] =$左端が $A_i$ で、長さが $2^j$ である区間の最小値

A         9  6  3  5  8  2 10  1  7  2

i=0
    j=0  |-|                            9
      1  |----|                         6
      2  |----------|                   3
      3  |----------------------|       1

これを計算しておくと、例えば $[2,8)$ の最小値は、以下のように求められる。

• クエリ区間の長さは 6
• それを超えない（$2^k \le 6$）最大の指数 $k$ は 2
• クエリ区間の左端と右端にあわせて $k=2$ の区間の事前計算結果を求める
• $\min(table[2][2], table[4][2])$ が答え

i            0  1  2  3  4  5  6  7  8  9
A            9  6  3  5  8  2 10  1  7  2
table[2][2]       |----------|               2
table[4][2]             |----------|         1
                                            ~~~→答えは1

PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。 （ただしminimum, maximumなど要素同士の演算を行う関数がNumPyに用意されているものに限る）