Answer many questions about the sum of part of a list that never changes.
What to build
A prefix-sum table that answers each range sum in one step.
Requirements
- Build the table of prefix sums once, as the numbers are read.
- For each question
l r, printa[l] + ... + a[r]. - Answer each question without a loop.
Input
The first line has n and q. The second line has the n numbers. Each of the next q lines has l and r. Positions start at 0.
Output
One line for each question.
Constraints
1 ≤ n, q ≤ 1000, 0 ≤ l ≤ r < n, and each number is from −1000 to 1000.
Example
Input:
5 3
5 8 6 3 2
0 4
1 2
3 3
Output:
24
14
3
Why it works
The sum up to r includes everything before l as well, so subtracting the sum before l leaves exactly the range. This is O(1) for each question, but only because nothing changes: one update would spoil every later prefix.
Examples
Example 1 · Input
5 3 5 8 6 3 2 0 4 1 2 3 3
Expected output
24 14 3
Example 2 · Input
1 1 -7 0 0
Expected output
-7
Hints
Hint 1
Make an array pre with n + 1 cells, where pre[0] is 0 and pre[i + 1] = pre[i] + a[i].
Hint 2
The sum of a[l] to a[r] is pre[r + 1] - pre[l].
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, q, pre[1001];
scanf("%d %d", &n, &q);
pre[0] = 0;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
pre[i + 1] = pre[i] + x;
}
for (int k = 0; k < q; k++) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d\n", pre[r + 1] - pre[l]);
}
return 0;
}