Prefix sum (6)
配列の区間に対して合計を計算する際、プレフィックスサムはとても便利です。毎回合計を求めるのではなく、あらかじめ配列のプレフィックスサムを用意しておけば、プログラムを何度も最適化できる可能性があります。
たとえば、要素数が非常に多いクエリ（「先頭から 番目までの合計はいくらか？」といった問い）を大量に処理したい場合を考えましょう。素朴な方法だと、毎回
a[0] + a[1] + ... + a[] を順番に足し上げることになります。a = [8, 3, -2, 4, 10, -1, 0, 5] # array
q = [3, 5, 2, 7] # queriesもし素朴な方法で求めると、それぞれのクエリに対して毎回ループを回して合計を計算することになり、同じ部分の足し算を何度も繰り返すことになります:
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]よく見ると、最初の部分にあたる計算は実は毎回重複しており、すでに計算済みの合計を再利用すれば、無駄を削減できるのがわかります。そこで、プレフィックスサム（prefix sum）を格納する配列
p を用意し、次のように計算します。p[i] には、元の配列 a の要素を先頭から i 番目まで足し合わせた値を保存しておきます。すると、任意のクエリ の答えは p[] を参照するだけで瞬時に求まります。pythonさらに、特定の要素を一度計算したら、次の要素は前の結果に足すだけで済むので、次のように書けます:python
このように、プレフィックスサムの配列を最初に一度だけ線形時間で計算しておけば、あとはどのクエリに対しても即座に答えを取り出せるようになるのです。つまり、p[i] が a[0] + a[1] + ... + a[i] の合計を表すので、クエリ の答えは単純に p[] になります。
「では、このプレフィックスサム配列はどのように計算すればいいのか？」という問題を考えてみましょう。
#### 入力
最初の行に整数 n (1 ≤ n ≤ $$10^5$$) が与えられます。
2 行目には、n 個の整数が空白区切りで与えられます。これは配列 a の要素を表します ($-10^9 < a_i < 10^9$)。
#### 出力
配列 a のプレフィックスサムにあたる配列を出力してください。
#### 例
| 入力 | 出力 |
|---------------------------------------|-----------------|
| 8<br/>8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
</topic>This can be calculated with a single
for loop in linear time instead of having multiple loops that do the same computation over and over. After computing the prefix sum array p, we will be able to answer all the queries instantly - as p[i] holds the information about the sum a[0] + a[1] + a[2] + ... + a[i]. So, for each query , the response will just be p[].Can you calculate the prefix sum array now?
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ). The second line of the input contains n space-separated integers representing the array a .Output
The program should output the prefix sum array of
a.Examples
Input | Output |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 20 MB