Sum any range in one subtraction

Picture a sales dashboard with eight years of daily revenue — about 2,900 numbers. A user clicks: "show me the total from March 2024 to August 2024." Then "and Q1 last year?" Then five hundred more queries before they're done.

The honest first thought: each click adds up the days in its range. For a million-day archive and a few hundred clicks, that's hundreds of millions of additions, mostly repeating work the previous query just did.

There's a precompute that takes a single O(n) pass and turns every future range query into one subtraction. Two array lookups, one minus sign, you're done — regardless of how wide the range is. The first time you see it, it feels almost illegal. It's called prefix sums, and once you have the trick you'll reach for it on dozens of problems.

Before you start

A for-loop is enough. This sits right next to two pointers, Kadane, and sliding window — same instinct: refuse to redo work the data already gave you.

The brute force, and why it bleeds

Each query, on demand, scans its range:

function rangeSum(a, l, r) {
  let s = 0;
  for (let i = l; i <= r; i++) s += a[i];
  return s;
}

Per query: O(width). Across q queries on n data points, you're paying O(n·q). And the waste is loud — the sum of [2, 8] shares almost everything with [3, 9] and [2, 7], and we throw it away every time.

So ask the smaller question that quietly answers the big one:

What's the sum from the very start of the array up to index i?

If you know that for every position, every range becomes a difference. Sum from l to r is just (sum from 0 to r) minus (sum from 0 to l − 1). A subtraction.

Define prefix[i] as the sum of the first i values:

prefix[0] = 0                  (empty — nothing yet)
prefix[1] = a[0]
prefix[2] = a[0] + a[1]
prefix[k] = a[0] + a[1] + ... + a[k-1]

Why prefix[0] = 0? Because then the formula has no edge cases — a sum that starts at index 0 just becomes prefix[r+1] - prefix[0] = prefix[r+1] - 0. The empty prefix is a freebie that makes the math identical for every range.

Now the punchline. For any l ≤ r:

sum(l..r) = prefix[r + 1] − prefix[l]

Two lookups. One subtraction. The range's width doesn't enter the cost at all.

Watch the magic land

A prefix array gets built once, then three different range queries get answered in a single subtraction each. Watch how the cost of the query never depends on how wide the range is:

loading visualization…

First the prefix array assembles itself, one element at a time. Then three queries land — each one answered by a single subtraction. Try your own array below.

You can see exactly where the magic lives: in the build phase, work is happening; in the query phase, nothing is being recomputed. The hard work was front-loaded into the precompute, and now every question costs the same — one subtraction — whether the range covers two elements or two million.

The whole thing, four ways

class RangeSum {
constructor(a) {
  this.p = [0];                              // the empty prefix
  for (const x of a) this.p.push(this.p[this.p.length - 1] + x);
}
sum(l, r) {                                  // inclusive on both ends
  return this.p[r + 1] - this.p[l];
}
}

const rs = new RangeSum([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rs.sum(2, 5));  // 19  ->  4 + 1 + 5 + 9

The whole technique is one expression: p[r + 1] - p[l]. The + 1 and prefix[0] = 0 aren't quirks — they're what kill the edge cases. Notice the C++ and Rust versions choose 64-bit (long long, i64) for the prefix array; sums grow fast, and a million 32-bit ints can overflow a 32-bit accumulator long before you finish building it.

What to take away

When to reach for it: many sum queries over a fixed array; "sum from a to b" asked repeatedly; counting things over ranges (run prefix sums on a 0/1 array — you get range counts the same way).
Complexity: O(n) to build, O(1) per query, O(n) extra space.
The gotcha: overflow on the prefix array. The values themselves fit in 32-bit; the cumulative sum can blow past that fast. Use 64-bit for the prefix.
The bigger family: the same idea lifts cleanly. 2D prefix sums answer rectangle queries on a grid in O(1) each (p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1] — same trick, two dimensions). Prefix XOR answers range-XOR queries by the identity xor(l..r) = prefix[r+1] ^ prefix[l]. And prefix sum + hashmap — count how many subarrays sum to exactly k — is one of the most-asked interview patterns in existence. Same shape every time: precompute, look up, subtract.

Key takeaway

Precompute partial sums once, with an empty prefix of 0 to kill edge cases. Every range query collapses to prefix[r+1] − prefix[l]. Two lookups, one subtraction — the range's width never matters again.

Try it yourself

Basic

Range Sum Query — Immutable — LeetCode 303. The canonical first prefix-sums problem; you're building exactly the class above.

Medium

Subarray Sum Equals K — LeetCode 560. The interview classic. Prefix sums meet a hashmap: for each prefix[i], ask the map how many earlier prefixes equal prefix[i] − k. That count is the answer for subarrays ending here.
Range Sum Query 2D — Immutable — LeetCode 304. The same trick in two dimensions. The formula has four terms instead of two — and that's the whole jump.

Hard

Number of Submatrices That Sum to Target — LeetCode 1074. The grown-up combination: 2D prefix sums plus the hashmap pattern from #560 applied to row pairs. Two ideas welded together.
Shortest Subarray with Sum at Least K — LeetCode 862. The boss fight. Prefix sums on an array with negatives, then a monotonic deque to find the shortest range whose prefix difference is ≥ K. This is where prefix sums stop being a trick and start being a technique.

The same instinct keeps surfacing across every post — Kadane, sliding window, two pointers, now this: refuse to redo work the data already gave you. Prefix sums are the algorithmic version of writing down your work so you don't redo it on the next problem. Each pattern you collect compounds on the last; by the time you've got five of these reflexes, problems that used to look hard start to look like recipes.