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, lcm, gcdなど2つの配列の要素同士の演算を行う関数がNumPyに用意されている
最小値の値そのものがわかればよく、最小値のindexは復元できなくてもよい

（※未バリデーション）

        
              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):
        """ min value of [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])

バリエーション

±1-RmQ

$A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の最小値/最大値を求める場合。

この場合、実装はちょっとややこしくなるが、クエリ応答は $O(1)$ のまま、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。

なかなか特殊な条件に見えるが、木の最小共通祖先だったり、たまに使える。

（とはいえ競プロの文脈では、logのあるなしだけでTLEになるケースは稀で、実装の手間からこちらを選ぶのはよほどあとちょっとで通らない場合に限られる）

概要は、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  0 -1 -1     0  0 -1 -2
 1     1  1     1     1  0     1    -1 -1     1    -1 -2
 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)$ より小さくなる。