累積和とfor文での和との対応

for文での和

例として、[3,6)の和をとるコードを書いてみると、以下のようになります。

a = [11, 31, 83, 25, 26, 94, 101]

s = 0
for i in range(3, 6):
    s += a[i]
print(s)

実行結果

145

累積和での和

累積和でも同様に書いてみます。

以下の記事を参考にして、先頭に0を追加しています。

累積和を何も考えずに書けるようにする！ - Qiita

0. はじめに最近では AtCoder がコーディング面接の文脈でも有効なものとしての認識が広まってきています。AtCoder の登竜門といわれる水色を目指すにあたって多くの方が「勉強した」と報告…

qiita.com

a = [11, 31, 83, 25, 26, 94, 101]
acc = [0] + list(itertools.accumulate(a))
print(acc[6]-acc[3])

実行結果

145

for文と累積和の対応

上記のように累積和をとるようにすると、for文のrange(i,j)とacc[j]-acc[i]が等しくなります。

つまり、以下のコードがエラーなく実行できます。

a = [11, 31, 83, 25, 26, 94, 101]
acc = [0] + list(itertools.accumulate(a))
for i in range(len(a)):
    for j in range(i, len(a)):
        s = 0
        for k in range(i, j):
            s += a[k]
        assert s == (acc[j] - acc[i])

これを覚えておくと、簡単に累積和が書けるようになるかもしれません。

累積和は配列のインデックスが訳分からなくなるので、何も考えずに書けるようになりたいです。