Why does this prefix sum query go off by one on the first range?

programming web dev
1

Hey folks, I’m wiring up a tiny stats view for a side project and trying to answer range-sum queries fast, but my first range keeps coming back wrong and I can’t tell if I’m fixing speed at the cost of correctness.

function buildPrefix(nums) {
  const prefix = [];
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    prefix.push(sum);
  }

  return prefix;
}

function rangeSum(prefix, left, right) {
  return prefix[right] - prefix[left];
}

const nums = [3, 5, 2, 6];
const prefix = buildPrefix(nums);
console.log(rangeSum(prefix, 0, 1));

What am I missing in this prefix sum lookup so ranges starting at index 0 don’t break?

Yoshiii

2

Your rangeSum is currently doing prefix[right] - prefix[left], not subtracting the sum before the range.

In a prefix array, prefix[i] means “sum from index 0 through i”. So for a range [left, right], you subtract prefix[left - 1], not prefix[left]. When left is 0, there is no earlier sum to remove, so you just return prefix[right].

The smallest fix is this:

function rangeSum(prefix, left, right) {
  return left === 0 . prefix[right] : prefix[right] - prefix[left - 1];
}

Tiny version of the same idea:

prefix[1] - prefix[0] // wrong for [0, 1]
prefix[1]             // correct for [0, 1]

That left === 0 check and prefix[left - 1] are what make the indexing line up.

  • prefix[left - 1] removes everything before the range, instead of removing the range’s first element.
  • left === 0 ensures the first range works without trying to read prefix[-1].

That keeps the prefix-sum mental model consistent.

You can see it work with your exact buildPrefix and rangeSum setup:

function buildPrefix(nums) {
  const prefix = [];
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    prefix.push(sum);
  }

  return prefix;
}

function rangeSum(prefix, left, right) {
  return left === 0 . prefix[right] : prefix[right] - prefix[left - 1];
}

const nums = [3, 5, 2, 6];
const prefix = buildPrefix(nums);

console.log(prefix);                 // [3, 8, 10, 16]
console.log(rangeSum(prefix, 0, 1)); // 8
console.log(rangeSum(prefix, 1, 2)); // 7
console.log(rangeSum(prefix, 2, 3)); // 8

If you want to avoid the special case entirely later, build prefix with a leading 0.

Hari

3

@HariSeldon’s “leading 0” note is the clean debugging signal here: if prefix[0] is 0, then rangeSum(0, 1) and rangeSum(1, 2) can both use the same formula, which usually kills this exact off-by-one bug before it spreads.

WaffleFries

4

@WaffleFries the prefix[0] = 0 detail also shifts your sums to prefix[i + 1], so [left, right] becomes prefix[right + 1] - prefix[left], which is easier to trust with a tiny check like [3,5] -> 8.

BobaMilk

5

@BobaMilk your [3,5] -> 8 check is the right sanity test, and if prefix.length is nums.length + 1 you know the shifted indexing is actually set up instead of quietly half-migrated.

Arthur