遅延伝播セグメント木 (Segment Tree with Lazy Propagation)
(DataStructure/SegmentTree/LazySegmentTree.py)

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

概要

列に対する区間作用、区間畳み込みを $O(\log n)$ で行えるデータ構造。作用素付きモノイドを要請する。

使い方

LazySegmentTree(n: int, unitX: T, unitA: U, X_f: Callable[[T, T], T], X_A: Callable[[U, U], U], XA_map: Callable[[T, U], T])
長さ $n$ の Lazy Segment Tree を構築する。計算量 $O(n)$ それぞれの演算について、

• 畳み込みの演算を二項演算 f_X、単位元 unitX として定義する。
• 作用素同士の演算を二項演算 f_A、単位元 unitA として定義する。ただし f_A(a, b) のとき、a が作用される作用素、b が作用する作用素である。
• 要素に対する作用を XA_map として定義する。ただし XA_map(x, a) のとき、x が作用される要素、a が作用する作用素である。

となる。

• build(array: List[T]) -> None
  Lazy Segment Tree を array で初期化する。計算量 $O(n)$

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

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

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

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

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

Required by

• DataStructure/SegmentTree/RMaxQ_RAQ.py
• DataStructure/SegmentTree/RMaxQ_RUQ.py
• RSQ_RMultipleQ (DataStructure/SegmentTree/RSQ_RMultipleQ.py)
• RSQ_RUQ (DataStructure/SegmentTree/RSQ_RUQ.py)
• RmQ_RAQ (DataStructure/SegmentTree/RmQ_RAQ.py)
• RmQ_RUQ (DataStructure/SegmentTree/RmQ_RUQ.py)

Code

class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  # (X, X) -> X
        self.A_f = A_f  # (A, A) -> A
        self.XA_map = XA_map  # (X, A) -> X
        self.X = [unitX] * (n + n)
        self.A = [unitA] * (n + n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        for i in range(self.n - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    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.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], 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 fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def range_apply(self, l, r, a):
        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.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)

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