RSQ_RMultipleQ
(DataStructure/SegmentTree/RSQ_RMultipleQ.py)

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

概要

列に対する区間乗算、区間和取得を $O(\log n)$ で行えるデータ構造。

使い方

RSQ_RMultipleQ(n: int)
区間乗算、区間和取得が可能な長さ $n$ の配列を構築する。配列の初期値は $0$ である。計算量 $O(n)$

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

• __getitem__(i: int) -> int
  $i$ 番目の要素を $998244353$ で割ったあまり返す。計算量 $O(\log n)$

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

• fold(l: int, r: int) -> int
  $[l, r)$ 番目の区間和を $998244353$ で割ったあまりを返す。計算量 $O(\log n)$

• apply(i: int, a: int) -> None
  $i$ 番目の要素を a 倍する。計算量 $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/AtCoder/abc221_e.test.py

Code

from DataStructure.SegmentTree.LazySegmentTree import LazySegmentTree


MOD = 998244353


class RSQ_RMultipleQ:
    def __init__(self, n):
        unitX = 0
        unitA = 1
        X_f = lambda x1, x2: (x1 + x2) % MOD
        A_f = lambda a1, a2: a1 * a2 % MOD
        XA_map = lambda x, a: x * a % MOD
        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