文書の過去の版を表示しています。
Sparse Table
概要
- 区間最小値/最大値など、区間に対するクエリに答えられる
- 演算 $\oplus$ は、以下の条件を満たす必要がある(min, maxなどに相当する部分)
- 結合則: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
- 冪等性: $A \oplus B = A \oplus B \oplus B \oplus ... \oplus B$
- クエリ処理はとても速い($O(1)$)
- 事前計算の計算量・メモリは少し多めに必要になる($O(N \log{N})$)
- 更新はできない
足し算は冪等性を満たさないため、使えない。 (別に使ってもいいのだが、区間を被らせずにクエリを処理するのは計算量 $O(\log{N})$ かかるし、 それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない)
データ構造
数列 $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$ を求める部分を高速化できる。
import numpy as np class SparseTable: def __init__(self, aaa): n = len(aaa) max_k = (n - 1).bit_length() - 1 INF = 10 ** 18 table = np.full((n, max_k + 1), INF, dtype=np.int64) table[:, 0] = aaa for k in range(1, max_k + 1): k2 = 1 << (k - 1) k3 = (1 << k) - 1 table[:n - k3, k] = np.minimum(table[:n - k3, k - 1], table[k2:n - k3 + k2, k - 1]) self.table = table def query(self, l, r): d = r - l if d == 1: return self.table[l, 0] k = (d - 1).bit_length() - 1 k2 = 1 << k return min(self.table[l, k], self.table[r - k2, k])