可換双対セグメント木 (Commutative Dual Segment Tree)
(DataStructure/SegmentTree/CommutativeDualSegmentTree.py)

• View this file on GitHub
• Last update: 2021-01-04 04:15:00+09:00

概要

列に対する区間作用、一点取得を $O(\log n)$ で行えるデータ構造。作用はモノイドに加えて可換性も要請するが、双対セグメント木 よりも高速。

使い方

CommutativeDualSegmentTree(n: int, unitA: T, A_f: Callable[[T, T], T])
長さ $n$ の Commutative Dual Segment Tree を構築する。作用は演算子 A_f、単位元 unitA によって定義される。計算量 $O(n)$

• __getitem__(i: int) -> T
  $i$ 番目の要素を返す。計算量 $O(\log n)$

• __setitem__(i: int, val: T) -> None
  $i$ 番目の要素を val に更新する。計算量 $O(1)$

• apply(i: int, val: T) -> None
  $i$ 番目の要素に val を作用させる。計算量 $O(\log n)$

• range_apply(l: int, r: int, val: T) -> None
  $[l, r)$ 番目の要素に val を作用させる。計算量 $O(\log n)$

Required by

• RUQ (DataStructure/SegmentTree/RUQ.py)

Code

class CommutativeDualSegmentTree:
    def __init__(self, n, unitA, A_f):
        self.n = n
        self.unitA = unitA
        self.A_f = A_f  # (A, A) -> A
        self.A = [unitA] * (n + n)

    def __getitem__(self, i):
        i += self.n
        res = self.unitA
        while i > 0:
            res = self.A_f(res, self.A[i])
            i >>= 1
        return res

    def __setitem__(self, i, val):
        i += self.n
        self.A[i] = val

    def apply(self, i, val):
        i += self.n
        self.A[i] = self.A_f(self.A[i], val)

    def range_apply(self, l, r, val):
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                self.A[l] = self.A_f(self.A[l], val)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.A_f(self.A[r], val)
            l >>= 1
            r >>= 1

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