双対セグメント木 (Dual Segment Tree)
(DataStructure/SegmentTree/DualSegmentTree.py)

• View this file on GitHub
• Last update: 2021-01-02 05:02:24+09:00

概要

列に対する区間作用、一点取得を $O(\log n)$ で行えるデータ構造。作用はモノイドを要請する。

使い方

DualSegmentTree(n: int, unitA: Any, A_f: Callable[[T, T], T])
長さ $n$ の Dual Segment Tree を構築する。作用は演算子 A_f、単位元 unitA によって定義される。A_f(a, b) のとき、a が作用される要素、b が作用する要素となることに注意。計算量 $O(n)$

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

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

• 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)$

Verified with

• TestCase/AOJ/DSL_2_D.test.py

Code

class DualSegmentTree:
    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
        self._propagate_above(i)
        return self.A[i]

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

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.A[i << 1 | 0] = self.A_f(self.A[i << 1 | 0], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

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

    def range_apply(self, l, r, val):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        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