Static Range Sums

Difficulty: 1100 3000 ms 128 MB

prefix-sums

Answer Q sum queries on a fixed array: each query asks for a_L + a_L+1 + … + a_R.

Input: the first line has N and Q; the second line has the N values; each of the next Q lines has L and R (1-based, inclusive).

Output: Q lines — the answer to each query in order.

Constraints:

• 1 ≤ N, Q ≤ 10⁴
• −10⁹ ≤ a_i ≤ 10⁹
• 1 ≤ L ≤ R ≤ N

Sample Tests

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

6
14
5

1 1
-7
1 1

-7

Read the Editorial