先頭０個を考慮しない二次元累積和を美しく書く

アドベントカレンダー（自称）vol.4

皆さん、こんにちは。yumyum116 です。SWE転職を目指す者です。
アドベントカレンダーに便乗して、1日1記事投稿に挑戦するとともに、執筆活動の習慣化にも挑戦してみます。

この記事は、概念は理解できても、プログラムに起こすことが苦手な自分が綴る、概念を実装してみたシリーズです。
自分と同じようなところで躓いている方、プログラミング初学者の方の参考になれば嬉しいです。

今回は、先頭０個を考慮しない二次元累積和を実装してみます。

予め書いておきますが、今回の実装は美しくありません。
未来の自分が、記事を見直して美しい実装を加筆修正するとともに、成長の実感を感じることを目的に記録用として書き残すものです。

1. 二次元累積和とは

累積和は、１次元配列の区間の和を指しますが、二次元累積和とは、二次元配列の長方形範囲の和を指します。

以下にイメージ図を示します。

式を用いて書くと、次のように記述できます。

$$s[x2 - x1][y2 - y1] = s[x2 + 1][y2 + 1] - s[x2 + 1][y1] - s[x2][y2 + 1] + s[x1][y1]$$

2. 要素数０個を考慮しない二次元累積和を求めるプログラムを実装してみる

「二次元累積和　プログラム」で検索すると、$i = 0$, $j = 0$ となる行および列に要素数 $n$ 分の $0$ を追加して求めるプログラムが出てくると思います。

単に二次元累積和を求めるだけのプログラムであれば、要素数0の場合の累積和が含まれていてもあまり気にならないかもしれませんが、求めた二次元累積和の結果を用いてさらに処理を行う場合などにおいては、要素数0の場合の累積和が含まれていると、少し扱いが煩雑になります。

そこで、要素数0個を考慮しない二次元累積和を求めるプログラムを考えてみます。
以下では、標準入力から $n * m$ の二次元配列 $A$ が与えられるものとします。

cumulative-sum-2d.py

def cumulative_sum_2d(array, n, m):
    cumulative_array = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(1, m):
            if  i == 0 and j == 0:
                cumulative_array[i][j] = a[i][j]
            elif i == 0:
                cumulative_array[i][j + 1] = cumulative_array[i][j] + array[i][j]
            elif j == 0:    
                cumulative_array[i + 1][j] = cumulative_array[i][j] + array[i][j]
            else:
                cumulative_array[i + 1][j + 1] 
                    = cumulative_array[i + 1][j] 
                    　+ cumulative_array[i][j + 1] - cumulative_array[i][j] 
                    　+ array[i][j]

未来の自分への期待ポイントは、i または j が０のときという条件分岐を書くことなく、実装することです。

この二次元累積和の考え方をどのような場面で使うのか？については、後日加筆修正したいと思います。

---

記事内に誤植等ございましたら、修正いたします。

それでは、また。