Sum of Ranges

2 secs 1024 MB
powell's icon powell

Sum of Ranges

問題

11 以上の整数 NN と、00 以上の整数 NN 個からなる数列 A={aN}A = \{a_N\} が与えられる。

QQ 個のクエリ (lj,rj)(l_j, r_j) に対して、alja_{l_j} から arja_{r_j} までの和 SjS_j、すなわち、

Sj=i=ljrjai=alj+alj+1++arjS_j = \sum_{i=l_j}^{r_j} a_i = a_{l_j} + a_{l_{j+1}} + \cdots + a_{r_j}

を求めよ。

制約

  • 1N1051 \le N \le 10^5
  • 1ai109 (1iN)1 \le a_i \le 10^9 ~(1\le i\le N)
  • 1Q1051 \le Q \le 10^5
  • 1ljrjN (1jQ)1 \le l_j \le r_j \le N ~(1\le j\le Q)

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 ... A_N
l_1 r_1
l_2 r_2
...
l_Q r_Q

出力

QQ 個のクエリについて、SjS_jNN 行で出力せよ。


入力例1

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

出力例1

6
9
15

11 個目のクエリでは 1+2+3=61 + 2 + 3 = 6 を出力します。
22 個目のクエリでは 2+3+4=92 + 3 + 4 = 9 を出力します。
33 個目のクエリでは 1+2+3+4+5=151 + 2 + 3 + 4 + 5 = 15 を出力します。


入力例2

8 3
31415 92653 58979 32384 62643 38327 95028 84197
1 3
2 7
1 8

出力例2

183047
380014
495626

Submit


Go (1.21)