RUQ
(DataStructure/SegmentTree/RUQ.py)

• View this file on GitHub
• Last update: 2022-04-24 23:38:04+09:00

概要

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

使い方

RUQ(n: int)
区間更新が可能な長さ $n$ の配列を構築する。配列の初期値は $0$ である。計算量 $O(n)$

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

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

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

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

Depends on

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

Verified with

• TestCase/AOJ/DSL_2_D.CommutativeDualSegTree.test.py

Code

from DataStructure.SegmentTree.CommutativeDualSegmentTree import CommutativeDualSegmentTree


class RUQ:
    def __init__(self, n):
        unitA = (0, 0)
        A_f = lambda a1, a2: a2 if a2 > a1 else a1
        self.st = CommutativeDualSegmentTree(n, unitA, A_f)
        self.cnt = 1

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

    def __setitem__(self, i, val):
        self.cnt += 1
        self.st[i] = (self.cnt, val)

    def apply(self, i, val):
        self.cnt += 1
        self.st.apply(i, (self.cnt, val))

    def range_apply(self, l, r, val):
        self.cnt += 1
        self.st.range_apply(l, r, (self.cnt, val))

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