Medium · prefix sums

Range Sum Queries

Adding up each range by hand costs O(range length) per question, and questions keep coming. Prefix sums move all the work to one preparation pass: prefix[i] is the sum of the first i numbers, so any range becomes one subtraction.

At a glanceBuild <code>prefix[i] = prefix[i-1] + a[i]</code> for i = 1..n once. The answer for [l, r] is <code>prefix[r] - prefix[l-1]</code> — one subtraction per query, with <code>long long</code> because the totals reach 10^13.

Problem

Input: The first line has n and q (1 ≤ n ≤ 10000, 1 ≤ q ≤ 10000). The second line has n integers (−10^9 ≤ a_i ≤ 10^9). Then q lines, each with l and r (1 ≤ l ≤ r ≤ n).

Output: q lines: for each query, the sum of a[l..r], one per line.

Samples:

Input	Output
`5 3 1 2 3 4 5 1 5 2 4 3 3`	`15 9 3`

The 1-based convention does quiet work here: prefix[0] = 0 makes the formula work for l = 1 without a special case. Off-by-one errors live exactly in this seam — see the demo below.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Define prefix[i] to include a[i]

Choose the meaning prefix[i] = a[1] + … + a[i] and set prefix[0] = 0. Then the sum of a[l..r] telescopes: everything up to r, minus everything before l. Half the off-by-one bugs in this problem come from mixing the two conventions.

Hint 2 — The array is 1-based, C++ is 0-based

Keep a[1..n] and prefix[1..n] at their natural indices: declare the arrays one slot bigger and simply ignore slot 0 (or store the 0 there). Fighting the convention with - 1 corrections sprinkled through the code is how sign errors are born.

Hint 3 — int cannot hold the sums

Each element fits in int (up to 10^9), but n of them add to 10^13 — far past int's ceiling of about 2.1 × 10^9. Make prefix a long long array. Overflow does not crash; it silently wraps to a wrong number, which is the nastiest kind of bug.

Solution (try it first!)

#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;

    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
    return 0;
}

Prefix sums are the first structure you build before knowing the questions — and the same idea returns in Maximum Subarray Sum, where a running prefix difference finds the best window in one pass. When updates join the queries, the next tool is a difference array; after that, trees.

Deep dive

Why this works

Store the running total. prefix[r] - prefix[l-1] cancels everything the two prefixes share, leaving exactly a[l] + … + a[r]. It is the same telescoping that makes sieve and counting-sort buckets fast: build a structure first, then answer from differences.

The cost

O(n) to build, O(1) per query, O(n) space. Brute force would be O(n·q) — with n = q = 10000 that is 100 million additions instead of 20 thousand.

Where it goes wrong

Answering prefix[r] - prefix[l] — it silently drops a[l]. The formula is prefix[l-1], and tests that only use l = 1 hide the bug.
Keeping prefix in int: each element fits, the total does not. Overflow wraps quietly and the answers merely look plausible.

Next step

The running-total trick returns as Kadane's insight in Maximum Subarray Sum — the best window is a difference of two prefixes.

Two things to remember

prefix[i] = a[1] + … + a[i]; a range is prefix[r] − prefix[l−1].
Sums of many ints need long long — overflow wraps quietly.

🐞 This version fails — open it and try

Answers prefix[r] - prefix[l] — quietly drops a[l]

#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l] << endl;
    }
    return 0;
}