累積和

pythonでの書き方の備忘メモ。
説明は下記記事が良い。

https://qiita.com/xryuseix/items/1059101a31107ba330d4

今まではDFSでやってしまいそうな問題だけど、これを使うと、ループが一つ減ることになる。

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)