How Prefix Sums Answer Range Queries
A prefix-sum array precomputes totals from the start. After O(n) preprocessing, any half-open range sum can be answered in O(1) by subtracting two prefixes.
A prefix-sum array stores cumulative totals so repeated range-sum questions do not rescan the same values. Define prefix[i] as the sum of elements before index i. Then the sum of the half-open range [start, end) is:
prefix[end] - prefix[start]
Why the subtraction works
prefix[end] contains everything before end): the values before startplus the requested range.prefix[start]contains exactly the unwanted values beforestart`. Subtracting cancels that shared prefix.
The initial zero is deliberate. It makes ranges beginning at index 0 use the same formula, and it gives an n-element input an n + 1-element prefix array.
Press Run to execute this example. Use console.log to print a value.
Expected output is [0, 3, 4, 8, 10], then 7, 4, and 0.
Trace the construction
Start with prefix = [0].
- Add 3 to 0, producing 3.
- Add 1 to 3, producing 4.
- Add 4 to 4, producing 8.
- Add 2 to 8, producing 10.
For [1, 4), subtract the total before index 1 from the total before index 4: 10 - 3 = 7. The included values are 1, 4, and 2.
Half-open ranges match slice(start, end): start is included and end is excluded. The empty range [2, 2) correctly has sum 0.
The construction invariant is: after processing i input values, prefix has length i + 1, and its last value is the sum of values[0] through values[i - 1]. The query formula then cancels two totals measured from the same origin.
Cost and trade-off
Building the prefix array takes O(n) time and O(n) extra space. Each range query then takes O(1) time and O(1) extra space.
For q queries, rescanning each range can cost O(qn) in the worst case. Prefix preprocessing makes the total O(n + q). The trade-off is worthwhile when the data is unchanged and there are many queries.
Changing one original value invalidates every later prefix total, so a simple prefix array is poor for frequent updates. More advanced structures such as Fenwick trees or segment trees balance updates and queries in O(log n).
Common mistakes
Do not omit the leading zero. Without it, ranges starting at index 0 need a special case.
Do not mix inclusive and exclusive end conventions. Write [start, end) next to the formula.
Do not rebuild the prefix array for every query. Build it once, then reuse it.
Do not use prefix sums blindly when totals can exceed JavaScript's safe integer range. number represents integers exactly only through Number.MAX_SAFE_INTEGER; integer-only applications with larger totals may need bigint.
When to use it
Use prefix sums for many aggregate queries over mostly immutable data. Besides sums, the same cancellation idea supports counts, such as “how many even values occur in this range?” by prefixing 1 for even and 0 for odd.
In the course
The leading zero, half-open range convention, cancellation formula, and O(n + q) analysis are core. The sliding-window exercise rangeSum uses the same cancellation with an inclusive right end: prefix[right + 1] - prefix[left] is the half-open span [left, right + 1). A prefix of [0] is an empty original array and that exercise returns 0. Fenwick trees, segment trees, and two-dimensional prefix sums are enrichment for workloads with updates or grid queries.
FAQ
Why is the prefix array one element longer?
The leading zero represents the sum before any values. It removes a boundary special case and makes prefix[end] - prefix[start] valid for every legal half-open range.
Are negative values allowed?
Yes. Prefix subtraction remains correct with negative values because it is an algebraic identity. Unlike the simple variable sliding window, it does not rely on sums changing monotonically.
When is preprocessing worth it?
Usually when multiple range queries reuse the same data. For one query, a direct scan is simpler and already O(n).