Sparse Table

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

2022/07/15 ブロック分割の項目を追加

概要

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

足し算は冪等性を満たさないため、使えない。
データの持たせ方を工夫した DisjointSparseTable なら可能。（ただ、そもそも足し算なら累積和で区間クエリには答えられる）

Disjoint Sparse Table

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

データ構造

数列 $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
i=1
    j=0     |-|                         6
      1     |----|                      3
      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])

バリエーション

ブロック分割

$A_0,...,A_{N-1}$ をあらかじめ $B$ 個ごとのブロックに分け、ブロックに対しSparse Tableを構築する手法。

活用シーン

主に以下の場合などに使われうる。

「$[l,r)$ の結果に $A_r$ を追加する」（区間を1伸ばす）計算量が、「$[l_1,r_1)$ と $[l_2,r_2)$ の結果同士をマージする」計算量より小さい
数列長 $N$ に比べ、クエリ数 $Q$ が小さい
通常のSparse Tableで $O(N \log{N})$ 個の情報を保存しておくにはメモリが足りない

特に1つめが成り立つときに効果が大きいが、単純なSparse Tableに比べ処理が煩雑になり、その分、定数倍もかさむので、劇的に改善することは期待しない方がよいかも。使いどころが難しい。

概要

「クエリ区間に完全に包括されるブロック区間」についてSparse Tableの前計算結果を利用し、はみ出た分は愚直に計算する。

 i    0  1 ... B-1 | B ... 2B-1 | 2B ... | 3B ... | 4B ... | 5B ... | 6B ... |
 
クエリ         |----------------------------------------------------------|

愚直に計算     |---|
table[1][2]        |---------------------------------------|
table[2][2]                     |-----------------------------------|
愚直に計算                                                          |-----|

以上をマージしてクエリの答えとする

計算量

例えば求めたい演算処理が、「区間を1つだけ広げる計算量は $O(x)$ だが、結果のマージには $O(y)$（$x \lt y$）かかるような性質」を持っていると、

全てをSparse Table化する場合
- 事前計算 $O(N y \log{N})$
- $Q$ 回のクエリ $O(Qy)$

ブロック分割する場合
- 事前計算 $O(Nx+\dfrac{N}{B}y\log{\dfrac{N}{B}})$
- $Q$ 回のクエリ $O(Q(Bx+y))$

クエリあたりの計算量を犠牲に、事前計算の計算量・メモリを減らすことができる。

事前計算とクエリのバランスを取るブロック長 $B$ はなかなか綺麗な形にはならないが、いろいろ端折って計算すると $B=\sqrt{\dfrac{Ny\log{N}}{Qx}}$ を目安に設定すればよさそう。

その場合、全体で $O(Nx+\sqrt{NQxy\log{N}}+Qy)$ となり、 $x \lt y, N \ge Q$ の場合に、全てをSparse Table化するより高速になることがわかる。

±1-RmQ

上記のブロック分割の考え方にさらに制約を課して、省メモリ化・高速化する手法。

概要

$A=\{A_0,A_1,...,A_{N-1}\}$ の要素が、必ず「左の値から1増えるか1減るかのどちらか」で変化していく配列の場合、その区間最小値や最大値は、クエリ応答は $O(1)$ のまま、事前計算量と空間を $O(N\log{N})$ から $O(N)$ に落とすことができる。
（結果のマージは $O(1)$ とする）

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

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

ブロック分割をベースの考え方として、「はみ出た部分」の計算をクエリ毎に愚直に行うのではなく、変化パターンが限られるのでパターン毎に事前計算しておくという発想。

B=3

 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]$ ごとに、最小値の左端要素からの差分配列を作っても、現実的な容量で間に合う。

ブロックサイズを $B$ とすると $B^22^{B-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$ のブロックは「++」パターンであり、はみ出ている区間は $[9, 9]$、ブロック内の相対的な位置になおすと $[2,2]$ なので、「++ テーブル」から $l=2,r=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)$ より小さくなる。

拡張性

必ずしも±1で遷移する場合に限定しなくても、ブロック内の変化パターン数が $2^B$ 程度で収まる場合、同じ理由で活用できそう。具体的にあるかは知らんけど。

目次