Sparse Table
(DataStructure/misc/SparseTable.py)

• View this file on GitHub
• Last update: 2021-01-03 09:10:09+09:00

概要

構築を $O(n\log n)$、区間畳み込みを $O(1)$ で行えるデータ構造。畳み込みは半群 + 冪等性を要請する。

使い方

SparseTable(array: Sequence[Any], op: Callable[[Any, Any], Any])
array を初期値とした Sparse Table を構築する。op は畳み込み計算で用いる二項演算子である。計算量 $O(n\log n)$

• fold(l: int, r: int) -> Any
  $\lbrack l, r)$ 番目の要素の畳み込み結果を返す。計算量 $O(1)$

Verified with

• TestCase/LibraryChecker/staticrmq.test.py

Code

class SparseTable:
    def __init__(self, array, op):
        self.n = len(array)
        self.row_size = self.n.bit_length()
        self.op = op

        self.log_tbl = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log_tbl[i] = self.log_tbl[i // 2] + 1

        self.sp_tbl = [0] * (self.n * self.row_size)
        for i in range(self.n):
            self.sp_tbl[i] = array[i]
        for row in range(1, self.row_size):
            prv_row = row - 1
            for i in range(self.n - (1 << row) + 1):
                self.sp_tbl[row * self.n + i] = \
                self.op(self.sp_tbl[prv_row * self.n + i],
                        self.sp_tbl[prv_row * self.n + i + (1 << prv_row)])

    def fold(self, l, r):
        row = self.log_tbl[r - l]
        return self.op(self.sp_tbl[row * self.n + l],
                       self.sp_tbl[row * self.n + r - (1 << row)])

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page