累積和
(DataStructure/AccumulateSum/AccumulateSum.py)

• View this file on GitHub
• Last update: 2021-01-01 19:51:50+09:00

概要

計算量 $O(n)$ の前計算により、列に対する区間和取得を計算量 $O(1)$ で行えるデータ構造。

使い方

AccumulateSum(array: Sequence[T])
大きさ $n$ の配列 array の累積和を構築する。計算量 $O(n)$

• sum(l: int, r: int) -> T
  $\lbrack l, r)$ 番目の要素の総和を返す。計算量 $O(1)$

Verified with

• TestCase/LibraryChecker/static_range_sum.test.py

Code

class AccumulateSum:
    def __init__(self, array):
        self.n = len(array)
        self.cumsum = [0] * (self.n + 1)
        for i, val in enumerate(array):
            self.cumsum[i + 1] = self.cumsum[i] + val

    def sum(self, l, r):
        return self.cumsum[r] - self.cumsum[l]

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