Safe sums and honest complexity
Choose wide types, avoid query-time copies, and recognize stale summaries.
The total needs its own bound
With up to 200000 values of magnitude 10⁹, an absolute prefix sum may reach 2 × 10¹⁴. Use long long for stored totals, arithmetic, and returned answers. A wide output variable does not repair an addition that already overflowed in int.
If a, b, and c are int, writing long long total = a + b + c still performs the additions as int. Widen before arithmetic, or read summands as long long. Signed overflow is undefined behavior, so the numeric bound is part of the algorithm’s correctness.
A constant-time query can hide a linear copy
Build a prefix array in O(n), answer each query with two indexed reads and subtraction in O(1), and spend O(n + q) overall. The prefix vector occupies O(n) storage. A helper should accept a const reference; passing the entire vector by value would copy n entries on every query.
The example streams directly into a prefix vector. A separate original array is optional: the old value a[i] can be recovered as P[i] − P[i − 1] while that summary remains unchanged.
// Complete C++23 program. Input: n q, n values, q valid inclusive ranges.
#include <iostream>
#include <vector>
long long rangeSum(const std::vector<long long>& pref, int l, int r) {
return pref[r] - pref[l - 1];
}
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 << rangeSum(pref, l, r) << '\n';
}
}Know what the summary cannot do
Changing a[2] changes every prefix from P[2] onward. Editing only the original array leaves its summary stale. A plain prefix array does not give fast interleaved updates and queries. Later difference arrays support a batch of additions before reconstruction, not arbitrary online queries.
Subtraction works because sums support cancellation. Prefix minimums lose information: for [1, 5, 4], the first two and first three minima are both 1, but the minimum of [2, 3] is 4. Subtracting those summaries gives zero. Derive a formula from the stored meaning instead of applying prefix subtraction to every operation.
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.
A program rebuilds all n prefixes before each of q queries. What is its total query-related work?
Turn the idea into code
Three values are each 1000000000. What should the full-range answer be? List the types and boundaries you would test in a rangeSum helper.
Give me a hint
Check where arithmetic happens, where it is stored, and what type the function returns.
Show the explained solution
The answer is 3000000000. Use long long summands, prefix entries, and return type, with a const-reference vector parameter. Test [1,1], [n,n], [1,n], an interior interval, all-negative input, and a sum above the 32-bit signed limit.
Your notes
Mark complete when you can explain it yourself.