Prefix sums and range queries

If a problem asks the same range question many times, spend O(n) once so each answer costs O(1).

A prefix sum array holds the running total: prefix[i] is the sum of the first i elements. The sum of any range then falls out of a subtraction.

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, in O(1).
const rangeSum = (prefix, from, to) => prefix[to + 1] - prefix[from];

The extra leading zero is not decoration — it removes the special case for ranges that start at index 0. Off-by-one bugs in prefix sums almost always come from omitting that slot.

The pattern that wins interviews

Count subarrays whose sum equals k, in one pass. Every subarray sum is a difference of two prefix sums, so instead of scanning for pairs, remember how many times each prefix value has occurred:

function countSubarraysWithSum(items, k) {
  const seen = new Map([[0, 1]]);   // empty prefix, once
  let running = 0;
  let count = 0;

  for (const item of items) {
    running += item;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }

  return count;
}

O(n) time and space, and — unlike a sliding window — it is correct with negative numbers.

Variations worth knowing

• Prefix XOR answers "subarray with XOR equal to k" the same way.
• Prefix counts per character answer "how many vowels between i and j".
• 2D prefix sums answer rectangle sums with four lookups, using inclusion–exclusion.
• Difference arrays are the mirror image: apply many range updates in O(1) each, then one pass to materialise the result.

When not to

If the array changes between queries, a static prefix array must be rebuilt each time — O(n) per update. That is the point where a Fenwick tree or segment tree earns its complexity, giving O(log n) updates and O(log n) queries.