Prefix Sums

A prefix sum stores cumulative information about everything before a position.

nums = [3, 1, 4, 2]
prefix = [0, 3, 4, 8, 10]

Range Query

prefix[r + 1] - prefix[l]

Implementation

function buildPrefix(nums: number[]) {
  const prefix = new Array(nums.length + 1).fill(0);

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

  return prefix;
}

Build is O(n) and each range query is O(1).

The same idea extends to prefix XOR, frequency prefixes, 2D prefix sums and difference arrays.