累積和
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)