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.