Build once. Query many times.
Derive prefix sums from their meaning and cancel the unwanted beginning.
Which work is repeated?
A range query asks about a consecutive part of a sequence. Scanning every requested interval is correct, but overlapping queries repeat additions. A worst case with n values and q queries needs O(nq) query work. When the values stay unchanged, store useful cumulative information once.
Static means the array does not change between queries. It does not require all queries to be known in advance: after preprocessing, you can read and answer them one at a time. If only one overall total is needed, a single running sum is enough; the prefix array is useful when different boundaries will be revisited.
Define an empty prefix
Let P[i] mean the sum of the first i input values. Then P[0] = 0 and P[i] = P[i − 1] + a[i]. For 4, −2, 7, 0, 3, the padded prefix array is 0, 4, 2, 9, 9, 12. Negative values can make prefixes decrease; no sortedness is required.
For n real positions numbered 1 through n, allocate n + 1 entries and reserve index 0. A prefix index measures how many values have been processed. The mathematical convention is one-based, but C++ vectors still have zero-based storage.
Subtract exactly the unwanted beginning
For inclusive positions [l, r], P[r] contains the desired interval plus everything before l. Subtract P[l − 1] to cancel only that beginning. Thus sum(l, r) = P[r] − P[l − 1]. For [2, 4], this is 9 − 4 = 5.
The zero prefix handles l = 1 without a special branch. A one-position interval gives P[l] − P[l − 1] = a[l]. For zero-based inclusive [L, R], the formula is P[R + 1] − P[L]; for half-open [L, R), it is P[R] − P[L]. Translate the interval contract instead of mixing conventions.
// Complete C++23 program. Input: n q, n values, q inclusive l r ranges.
// Contract: 1 <= l <= r <= n; n,q <= 200000; |value| <= 1e9.
#include <iostream>
#include <vector>
int main() {
int n, q;
std::cin >> n >> q;
std::vector<long long> pref(n + 1, 0);
for (int i = 1; i <= n; ++i) {
long long value;
std::cin >> value;
pref[i] = pref[i - 1] + value;
}
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << pref[r] - pref[l - 1] << '\n';
}
}Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
For [4, −2, 7, 0, 3], what is the sum of one-based positions [3, 3]?
Turn the idea into code
Build every padded prefix for [6, −4, 2]. Answer one-based [1, 3] and [2, 3], then translate [2, 3] into a zero-based half-open interval.
Give me a hint
There are four prefix lengths: 0, 1, 2, and 3.
Show the explained solution
P = [0, 6, 2, 4]. The full sum is 4 − 0 = 4. Positions [2, 3] sum to 4 − 6 = −2. They are zero-based indices [1, 3), so the same answer is P[3] − P[1].
Your notes
Mark complete when you can explain it yourself.