Python で書く累積和

競技プログラミングをしているときにパッと出てこなかったので備忘として。

そもそもどういうときに使用するか？

N の長さを持つ配列中のある区間の総和を知りたいとき。
かかるものとしては
・前処理に O(N)]
・記憶容量に O(N)
・クエリ計算時間結果に O(1)

長さ N の配列 A に対して S[ i  + 1 ] = S [ i ] + A[ i ] ( i は 0 ~ N の数値）という配列 S を定義することにより以下のように累積和が計算できる。

A = [3, 8, 2, 9, 3, 9, 10, 6]
N = len(A)

S = [0]
for i in range(0, N):
 S.append(S[i] + A[i])

# 配列A の区間 1 ~ 3 の総和は
S_1_3 = S[3] - S[1]
print(S_1_3)