Atcoderで累積和が出てきたのでこれを機にちょっと勉強する

累積和とは

サイズNの配列があって、ある区間iからjまでの和$(0<=i<j<=N)$を爆速で取り出すことができるアルゴリズム。

すでに先人達が多くの解説記事を上げているので、詳細な解説はここでは書かない。
（個人的にはけんちょんさんの記事がわかりやすかった）
累積和を何も考えずに書けるようにする！

Pythonで累積和を実装する

脳筋実装すればこうなる。

# 1~10のリスト
a = [1,2,3,4,5,6,7,8,9,10]

# 累積和用リスト
s = [0] * 10

s[0] = a[0]

for i in range(1, 10):
        s[i] = s[i-1] + a[i]
print(s) # [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

例えば、インデックスが3〜7の区間の和を取りたければ7までの和 ー 2までの和で求めることができる。

print(s[6] - s[1]) #25

こういった配列sを作る方法は上に上げた脳筋forループの他にもいくつかあるが、pythonを使う上で一番早いのはおそらくNumpy.cumsumである。

速度については下記記事で検証されているので、気になる方はどうぞ。
リストから和のリストを得る（累積和）

cumsumの使い方は↓

import numpy as np
# 1~10のリスト
a = [1,2,3,4,5,6,7,8,9,10]

# 累積和用リスト
s = np.cumsum(a)
print(s) # [ 1  3  6 10 15 21 28 36 45 55]

Pythonは便利なライブラリが多くていいですね。