この問題は、ソースコードを公開に設定しているので、
暇な人は初めてこの問題に取り組む人の為に
分かりやすいソースコードを提出してくださると助かります。
累積和
ある区間までの値の総和を求めるときなどに使います。
累積和を用いた配列の 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 ≦ Datai ≦ 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 3Sumの 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 と等しくなります。