Disjoint Sparse Table
(DataStructure/misc/DisjointSparseTable.py)

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

概要

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

使い方

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

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

参考

Disjoint Sparse Table と セグ木に関するポエム

Verified with

• TestCase/LibraryChecker/static_range_sum.DisjointSparseTable.test.py
• TestCase/LibraryChecker/staticrmq.DisjointSparseTable.test.py

Code

class DisjointSparseTable:
    def __init__(self, array, op):
        self.n = len(array)
        self.op = op
        self.row_size = self.n.bit_length()
        self.log_tbl = [0] * (1 << self.row_size)
        for i in range(2, 1 << self.row_size):
            self.log_tbl[i] = self.log_tbl[i // 2] + 1

        self.sp_tbl = [[0] * self.n for _ in range(self.row_size)]
        for i, val in enumerate(array):
            self.sp_tbl[0][i] = val
        for row in range(1, self.row_size):
            shift = 1 << row
            l = 0
            while l < self.n:
                mid = l + shift
                t = min(mid, self.n)
                self.sp_tbl[row][t - 1] = array[t - 1]
                for k in reversed(range(l, t - 1)):
                    self.sp_tbl[row][k] = self.op(array[k], self.sp_tbl[row][k + 1])
                if self.n <= t:
                    break
                r = min(mid + shift, self.n)
                self.sp_tbl[row][t] = array[t]
                for k in range(t + 1, r):
                    self.sp_tbl[row][k] = self.op(self.sp_tbl[row][k - 1], array[k])
                l = mid + shift

    def fold(self, l, r):
        r -= 1
        if l == r:
            return self.sp_tbl[0][l]
        p = self.log_tbl[l ^ r]
        return self.op(self.sp_tbl[p][l], self.sp_tbl[p][r])

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