paiza 累積和メニュー 区間の和 1 Python解説

スポンサーリンク

区間の和 1

10 個の整数 a_0, a_1, a_2, …, a_9 からなる数列 a が与えられます。
a_0, a_1, a_2, …, a_9 をそれぞれ

1 5 9 7 5 3 2 5 8 4

としたとき、この数列の a_2 から a_7 までの和 (a_2 + a_3 + … + a_7) を、累積和を使うことで求めてください。

paizaラーニング「区間の和 1」

累積和とは、適切な前処理を行うことによって、配列上の区間のクエリを高速で処理することができるアルゴリズムです。

今回の問題ではあらかじめ数列aの累積の和を求めておくことで、a_2からa_7までの和を計算します。

a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
s = [0] * 11
s[0] = 0

for i in range(10):
    s[i + 1] = s[i] + a[i]
    
print(s[8] - s[2])

数列aの累積の和を入れておく配列sを定義します。配列の先頭にs[0] = 0を入れたいので、全体の配列の長さは数列aの長さ+1になります。

あとは、s[i + 1] = s[i] + a[i]で配列sを求め、最後にa_2からa_7までの和を出力して完了です。
a_2からa_7までの和はs[8] – s[2]になります。