文書の過去の版を表示しています。


Sparse Table

概要

  • 区間最小値/最大値など、区間に対するクエリに答えられる
  • 演算 $\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に用意されているものに限る)

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])

programming_algorithm/data_structure/sparse_table.1575453699.txt.gz · 最終更新: 2019/12/04 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0