002 - プログラミング入門：累積和

この問題は、ソースコードを公開に設定しているので、
暇な人は初めてこの問題に取り組む人の為に
分かりやすいソースコードを提出してくださると助かります。

累積和

ある区間までの値の総和を求めるときなどに使います。
累積和を用いた配列の i番目には、
データの0番目からi番目までの値の総和が格納されています。
データが入っている配列を Data、
累積和が入っている配列を Sum とし、
Sum のi番地目の値を数式で示すと、以下のようになります。

Sum[i] = Sum[i-1] + Data[i]

今回はこの処理を行う為、Sum[0]の値は0にしておいてください。
このとき、 番地a から 番地b までの区間の和は、

Sum[b] - Sum[a-1] 

となります。
これは、
データの一番目からb番目までの総和から、
データのa-1番目までの総和を引くと、
データのa番目からb番目までの総和を求めることが出来るからです。
なにか分からないことがあれば先輩に聞いてください。
それでは、以下の問題を解いてみてください。

問題

N個の整数データと、M個の命令が与えられます。
データは与えられる順に、1,2,3, ... ,N 個目と表します。
命令は以下のようになっています。

a b

この命令では、
a と b が入力されるので、
データのa個目の値からb個目の値までの総和を出力してください。
詳しくは、入出力例を参考にしてください。

制約

• 1 ≦ N,M ≦ 1,000,000
• 0 ≦ Data_i ≦ 100
• 1 ≦ a ≦ b ≦ N

注意

累積和を行う配列の大きさは、
N+1必要になることに注意してください。

入出力形式

入力形式

N
Data1 Data2 ... DataN
M
a1 b1
a2 b2
..
..
..
aM bM

出力形式

データの入力後、累積和の処理を行った 配列Sum の
0番地目 から N番地目 までの値を空白区切りで出力し、
命令毎に、データのa番目からb番目までの総和を出力して改行してください。

入出力例

入力例一

6
1 2 3 4 5 6
3
2 4
1 6
3 3

出力例一

0 1 3 6 10 15 21
9
21
3

Sumの 1番地には Sum[0] に Data[1] を足したものが入るため、
0 + 1 = 1 となります。
Sumの 2番地には Sum[1] に Data[2] を足したものが入るため、
1 + 2 = 3 となります。

データの2番目から4番目までの総和は、
2 + 3 + 4 = 9 となります。
これは、
Sum[4] - Sum[2-1] = 10 - 1 = 9 と等しくなります。