二次元累積和
(DataStructure/AccumulateSum/AccumulateSum2D.py)

• View this file on GitHub
• Last update: 2021-01-02 00:00:29+09:00

概要

計算量 $O(hw)$ の前計算により、二次元配列に対する矩形和取得を計算量 $O(1)$ で行えるデータ構造。

使い方

AccumulateSum2D(matrix: Sequence[Sequence[T])
二次元配列 matrix に対して、二次元累積和を構築する。matrix のサイズを $h × w$ としたとき、計算量 $O(hw)$

• sum(hl: int, hr: int, wl: int, wr: int) -> T
  矩形範囲 $\lbrack hl, hr) × \lbrack wl, wr)$ の要素の総和を返す。計算量 $O(1)$

Verified with

• TestCase/AOJ/0098.test.py
• TestCase/AOJ/0560.test.py

Code

class AccumulateSum2D:
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.cumsum = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.cumsum[i + 1][j + 1] = self.cumsum[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.cumsum[i + 1][j + 1] += self.cumsum[i][j + 1]

    def sum(self, hl, hr, wl, wr):
        """sum of values in range [hl, hr) * [wl, wr)"""
        return (self.cumsum[hr][wr] + self.cumsum[hl][wl]
                - self.cumsum[hr][wl] - self.cumsum[hl][wr])

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