Prefix Sums and Range Queries

If a problem asks the same question about many different ranges, precompute once rather than re-scanning for every query.

Prefix sums

Build an array where each entry holds the total of everything before it. The sum of any range is then the difference of two entries - one subtraction, regardless of how wide the range is.

function buildPrefix(items) {
  const prefix = new Array(items.length + 1).fill(0)
  for (let i = 0; i < items.length; i++) {
    prefix[i + 1] = prefix[i] + items[i]
  }
  return prefix
}

// Sum of items[from..to], inclusive.
function rangeSum(prefix, from, to) {
  return prefix[to + 1] - prefix[from]
}

const items = [3, 1, 4, 1, 5, 9, 2, 6]
const prefix = buildPrefix(items)

console.log(rangeSum(prefix, 2, 5))  // 19
console.log(rangeSum(prefix, 0, 7))  // 31

The extra leading zero is what removes the special case for a range starting at index 0. It is worth the one wasted slot.

The subarray-sum trick

Combine prefix sums with a hash map and you can count subarrays summing to a target in one pass. If prefix[j] - prefix[i] === target, then prefix[i] === prefix[j] - target - so at each position you look up how many earlier prefixes had the required value.

function countSubarrays(items, target) {
  const seen = new Map([[0, 1]])   // one empty prefix
  let running = 0
  let count = 0

  for (const value of items) {
    running += value
    count += seen.get(running - target) || 0
    seen.set(running, (seen.get(running) || 0) + 1)
  }

  return count
}

console.log(countSubarrays([1, 1, 1], 2))       // 2
console.log(countSubarrays([3, 4, 7, 2, -3, 1, 4, 2], 7))  // 4

This is the technique that replaces a sliding window when the array can contain negative numbers - the case where a window has no valid direction to move.

When the data changes

Prefix sums assume the array is static. One update invalidates everything after it, costing O(n) to rebuild. If updates and queries are interleaved, you need a structure that supports both in logarithmic time.

class Fenwick {
  constructor(size) {
    this.size = size
    this.tree = new Array(size + 1).fill(0)
  }

  // Add delta at index i (zero-based).
  update(i, delta) {
    for (let x = i + 1; x <= this.size; x += x & -x) {
      this.tree[x] += delta
    }
  }

  // Sum of [0..i], inclusive.
  prefix(i) {
    let total = 0
    for (let x = i + 1; x > 0; x -= x & -x) {
      total += this.tree[x]
    }
    return total
  }

  range(from, to) {
    return this.prefix(to) - (from > 0 ? this.prefix(from - 1) : 0)
  }
}

const tree = new Fenwick(8)
;[3, 1, 4, 1, 5, 9, 2, 6].forEach((v, i) => tree.update(i, v))

console.log(tree.range(2, 5))   // 19
tree.update(3, 10)              // items[3] becomes 11
console.log(tree.range(2, 5))   // 29

x & -x isolates the lowest set bit - the same trick from the bit manipulation lesson - and that is what makes each step jump over a whole block of indices, giving O(log n).

Choosing

• Static data, many range queries - prefix sums. Simplest, O(1) per query.
• Updates and sum queries interleaved - Fenwick tree. O(log n) each, compact code.
• Range minimum, maximum, or custom merges - a segment tree. More code, but it handles operations a Fenwick tree cannot.
• Two dimensions - the same prefix idea with inclusion-exclusion over four corners.