RmQ_RUQ
(DataStructure/SegmentTree/RmQ_RUQ.py)

• View this file on GitHub
• Last update: 2022-04-25 00:19:30+09:00

概要

列に対する区間更新、区間最小値取得を $O(\log n)$ で行えるデータ構造。

使い方

RmQ_RUQ(n: int)
区間更新、区間最小値取得が可能な長さ $n$ の配列を構築する。配列の初期値は (1 << 31) - 1 である。計算量 $O(n)$

• build(array: List[int]) -> None
  配列を array で初期化する。計算量 $O(n)$

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

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

• fold(l: int, r: int) -> int
  $[l, r)$ 番目の区間最小値を返す。計算量 $O(\log n)$

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

• range_apply(l: int, r: int, a: int) -> None
  $[l, r)$ 番目の要素を a に更新する。計算量 $O(\log n)$

Depends on

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

Verified with

• TestCase/AOJ/DSL_2_F.test.py

Code

from DataStructure.SegmentTree.LazySegmentTree import LazySegmentTree


class RmQ_RUQ:
    def __init__(self, n):
        unitX = (1 << 31) - 1
        unitA = None
        X_f = min
        A_f = lambda a1, a2: a1 if a2 == unitA else a2
        XA_map = lambda x, a: x if a == unitA else a
        self.st = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map)

    def build(self, array):
        self.st.build(array)

    def __getitem__(self, i):
        return self.st[i]

    def __setitem__(self, i, x):
        self.st[i] = x

    def fold(self, l, r):
        return self.st.fold(l, r)

    def apply(self, i, a):
        self.st.apply(i, a)

    def range_apply(self, l, r, a):
        self.st.range_apply(l, r, a)

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