Prefix sum
配列内の区間（範囲）を扱うときに、Prefix sum（累積和）は非常に便利です。配列の合計を毎回計算する代わりに、あらかじめ累積和を計算しておくことで、多くの場合処理を高速化できます。
たとえば、「配列
a の先頭から 番目までの要素の合計は？」というクエリ（大量、たとえば何百万回）に答える必要がある状況を考えてみましょう。素朴な方法は、a[0] + a[1] + a[2] + ... + a[] を毎回計算することです。例として、配列とクエリが次のようになっているとします:a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesこれを素直に
for ループで計算すると、以下のように何度も重複した計算を行ってしまいます:res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]見てわかるように、最初の部分の計算は毎回同じです。たとえば
res2 を求める前に、res1 で a[0] + a[1] + a[2] + a[3] はすでに求めてありました。res4 を計算する前にも、a[0] + a[1] + a[2] + a[3] + a[4] + a[5] は先のステップで計算済みです。このように、同じ計算を何度も重複させるのは非効率で、クエリに即応できるように最適化が可能です。そこで、元の配列
a の要素を先頭から順に合計した値を保存する、Prefix sum（累積和）の配列 p を用意します。そうすれば、求めたい区間の合計は p の要素を見るだけで即座に得られます。以下のように、p の各要素はそれまでの要素をすべて足したものになります:p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]ここでは、次の要素を計算するときに、ひとつ前の累積和に新しい要素を加えるだけで済んでいます。新しい値を求める際に、毎回全部の要素を足し合わせる必要はありません:
p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]このように、単一の
for ループで累積和を線形時間で計算できます。いったん p ができあがれば、クエリの答えは p[] を返すだけで済むので、高速に応答できます。それでは、この累積和の配列を計算してみましょう。
Input
最初の行に整数
n (1 ≤ n ≤ ) が与えられます。次の行には、配列 a の要素が n 個、スペース区切りで与えられます。Output
配列
a の累積和を出力してください。Examples
入力 | 出力 |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 20 MB