Prefix Sums for Fast Range Queries

The sliding-window lesson showed one way to avoid re-summing overlapping ranges: maintain a running total as a fixed window moves. Prefix sums generalize that idea to answer any range-sum query — not just a moving window of fixed size, but an arbitrary "sum from index i to index j," picked after the fact and possibly repeated many times with different i and j.

The problem this solves

A dashboard has an array of 10,000 daily revenue numbers. A user drags a date range slider, and on every frame of that drag, the chart needs "total revenue between day i and day j" for a new i and j.

// The naive way: re-sum the range every single time it's asked for.
function sumBetween(data, i, j) {
  let total = 0;
  for (let k = i; k <= j; k++) total += data[k];
  return total;
}

One call is O(range length) — fine in isolation. But a drag gesture can fire dozens of these per second, each over a range that might be thousands of entries wide. That's the "cheap-looking operation called repeatedly" trap from this course's very first lesson, and it's exactly what prefix sums are for.

Precompute once, query in O(1)

function buildPrefixSums(data) {
  const prefix = new Array(data.length + 1).fill(0);
  for (let i = 0; i < data.length; i++) {
    prefix[i + 1] = prefix[i] + data[i];
  }
  return prefix;
}
 
function rangeSum(prefix, i, j) {
  // sum of data[i..j] inclusive
  return prefix[j + 1] - prefix[i];
}

prefix[k] is defined as "the sum of the first k elements of the original array" — so prefix[0] is 0 (sum of zero elements), prefix[1] is data[0], prefix[2] is data[0] + data[1], and so on. That single extra slot at the front (prefix[0] = 0) is what makes the subtraction formula work cleanly even when the range starts at index 0.

To get the sum from i to j inclusive: prefix[j + 1] is "everything up to and including j," and prefix[i] is "everything strictly before i." Subtract the second from the first, and what's left is exactly the range you asked for — no loop required.

data:    [ 3,  1,  4,  1,  5,  9,  2,  6 ]
index:     0   1   2   3   4   5   6   7

prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
index:   0  1  2  3  4   5   6   7   8

Sum of data[2..5] (the values 4, 1, 5, 9, which total 19): prefix[6] - prefix[2] = 23 - 4 = 19. Correct, and it took one subtraction regardless of how wide the range was.

The trade, made explicit

Building the prefix array costs O(n) time and O(n) auxiliary space (a second array the same length as the original, plus one). That's a real cost, paid once. What you get in exchange is every subsequent range query dropping from O(range length) to O(1) — a trade that pays for itself the moment you make more than a handful of queries against data that isn't constantly changing underneath you.

That last condition matters. If the underlying data mutates between every query — new revenue numbers streaming in constantly — you either eat the cost of rebuilding the whole prefix array (right back to O(n) per update) or need a more sophisticated structure built for efficient updates (a Fenwick tree / binary indexed tree, or a segment tree — real structures, genuinely out of scope for a frontend-interview-focused course, but worth knowing they exist if you ever hit "many updates and many range queries" at the same time). For "build once, query many times against mostly-static data" — a fixed report, a rendered chart's dataset, a scrollback buffer — prefix sums are the right-sized tool.

What to remember

• A prefix sum array turns "sum of a range" from an O(range length) scan into an O(1) lookup, after a one-time O(n) build.
• The formula is prefix[j + 1] - prefix[i] for an inclusive range [i, j], where prefix[k] means "sum of the first k elements" and prefix[0] = 0.
• The trade only pays off when you query the same (mostly static) data many times — if the underlying data changes on every query, rebuilding wipes out the benefit, and you'd want a structure built for fast updates instead.
• This is the same "maintain a running total instead of recomputing" instinct as the sliding window lesson, generalized from a fixed-size moving window to an arbitrary range picked after the fact.