Prefix Sum — Range Queries

Practice this coding question on Coding Gurukul.

Problem statement

Given an array and q queries l r, print the sum of the elements from index l through index r, including both endpoints. Indices are zero-based. The array does not change. Build prefix sums once in O(n) time and answer each query in O(1) time. Values and sums may be negative. Use signed 64-bit sums. If l=r, print the value at that index. Worked example For [3, -2, 5, 1], ranges [0, 2], [1, 3] and [2, 2] have sums 6, 4 and 5.

Input format

First line: n q. Second line: n integers. Next q lines: l r.

Output format

Print one sum per query.

Constraints

1 <= n,q <= 100000; -10^9 <= a[i] <= 10^9; 0 <= l <= r < n.

Sample input

4 3
3 -2 5 1
0 2
1 3
2 2

Sample output

6
4
5

Sign in to run or submit a solution in C++, Java or Python.