いもす法 (等差数列加算)
(DataStructure/AccumulateSum/ImosArithmeticSequence.py)

• View this file on GitHub
• Last update: 2022-09-11 12:52:50+09:00

使い方

ImosImosArithmeticSequence(n: int)
大きさ $n$ のいもす法用の配列を初期構築する。計算量 $O(n)$
その後の一連の処理としては

1. add 関数で等差数列加算の準備をする。
2. build 関数で等差数列加算を実行する。
3. __getitem__ 関数で値を取得する。

となる。

• add(l: int, r: int, a: int, d: int) -> None
  区間 $[l, r)$ に対して $a, a + d, a + 2 * d, \dots , a + d * (r - l + 1)$ を足す準備をする。計算量 $O(1)$

• build() -> None
add による等差数列加算を実行する。計算量 $O(n)$

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

Code

class ImosArithmeticSequence:
    def __init__(self, n):
        self.n = n
        self.imos0 = [0] * (self.n + 1)
        self.imos1 = [0] * (self.n + 1)

    def __getitem__(self, i):
        return self.imos0[i] + self.imos1[i] * i

    def add(self, l, r, a, d):
        self.imos0[l] += a
        self.imos0[r] -= a
        self.imos0[l] -= d * l
        self.imos0[r] += d * l
        self.imos1[l] += d
        self.imos1[r] -= d

    def build(self):
        for i in range(self.n):
            self.imos0[i + 1] += self.imos0[i]
            self.imos1[i + 1] += self.imos1[i]

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