Pythonで2次元累積和（接頭辞和）行列を求める方法：各要素が左上領域の合計になる行列の作り方

問題の概要

ある行列が与えられたとき、同じサイズを持つ新しい行列 res を求めることを考えます。この新しい行列の各要素は、次のように定義されます。

res[i][j] = 元の行列における matrix[r][c] の合計（ただし r ≤ i かつ c ≤ j を満たすすべての要素）

つまり、各位置 (i, j) には「その位置から見て左上側にあるすべての要素の合計」が入ります。これはいわゆる2次元累積和（Prefix Sum）と呼ばれる手法で、画像処理や動的計画法など、さまざまな分野で活用される重要なテクニックです。

入力例

出力例

例えば、右下の要素 21 は元の行列の全要素（8 + 2 + 7 + 4）の合計になっています。また、右上の 10 は 8 + 2、左下の 15 は 8 + 7 の合計です。

解き方のアルゴリズム

この問題は、以下の手順で効率的に解くことができます。ポイントは行方向の累積和 → 列方向の累積和という順番で2回走査することです。

1. 行列が空の場合は、そのまま空の行列を返します。
2. R を行数、C を列数として取得します。
3. r = 1 から R - 1 までの各行について、c = 0 から C - 1 までの各列に対して次の処理を行います：
   matrix[r][c] += matrix[r-1][c]
   これにより、各行に「上方向の累積和」が加算されます。
4. 続いて、r = 0 から R - 1 までの各行について、c = 1 から C - 1 までの各列に対して次の処理を行います：
   matrix[r][c] += matrix[r][c-1]
   これにより、「左方向の累積和」が加算され、最終的な結果が得られます。
5. 更新された行列を返します。

この方法なら、時間計算量は O(R × C)、つまり行列の要素数に比例するだけで済みます。各セルごとに左上の全要素を毎回足し直す素朴な実装（O(R² × C²)）と比べて、大幅に高速です。

Pythonでの実装例

以下のコードは、上記のアルゴリズムをPythonで実装したものです。

def solve(matrix):
    if not matrix:
        return matrix

    R, C = len(matrix), len(matrix[0])

    # 行方向（上からの累積和）
    for r in range(1, R):
        for c in range(C):
            matrix[r][c] += matrix[r - 1][c]

    # 列方向（左からの累積和）
    for r in range(R):
        for c in range(1, C):
            matrix[r][c] += matrix[r][c - 1]

    return matrix

matrix = [
    [8, 2],
    [7, 4]
]
print(solve(matrix))

入力

[[8, 2], [7, 4]]

出力

[[8, 10], [15, 21]]

まとめ

この記事では、与えられた行列の各要素について「その位置より左上にある全要素の合計」を格納した新しい行列をPythonで求める方法を紹介しました。行方向と列方向の2回の走査だけで完成するため、計算量は O(R × C) と非常に効率的です。2次元累積和は、部分矩形の合計を高速に取得したい場合などにも応用できる便利なテクニックなので、ぜひ覚えておきましょう。