← All coding problems
Range Sum Queries
easyArrays & Prefix Sums+10 XPTime limit 2s
A shop keeps its sales of each day in an array. The manager asks many questions of the form "what were the total sales from day l to day r?". Answer every question.
Input:
- line 1:
n - line 2:
nintegers (sales can be negative — refunds) - line 3:
q - next
qlines:l r(1-based,l ≤ r)
Output: q lines — the sum of a[l..r] for each query.
Constraints: 1 ≤ n, q ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹ (sums need 64-bit integers).
Think about it: adding up the range for every query is O(n·q). Build a prefix sum array once: p[i] = sum of the first i elements. Then any range sum is p[r] − p[l − 1], in O(1).
Sample input 1
5 3 -1 4 1 5 3 1 3 2 5 4 4
Sample output 1
6 9 1
Sample input 2
1 7 2 1 1 1 1
Sample output 2
7 7
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).