Prefix Sums

What is a Prefix Sum Array?

Given an array nums, its prefix sum array prefix is an array where prefix[i] is the sum of all elements from nums[0] up to nums[i-1]. It's common to make the prefix sum array one element longer than the original to simplify calculations.

prefix[k] = nums[0] + nums[1] + ... + nums[k-1]

It can be calculated efficiently in O(n) time:

# Python for creating a prefix sum array
def create_prefix_sum(nums):
  n = len(nums)
  prefix = [0] * (n + 1)
  for i in range(n):
    prefix[i+1] = prefix[i] + nums[i]
  return prefix

Solving Range Sum Queries

The primary application of a prefix sum array is to answer "range sum queries" in O(1) time. A range sum query asks for the sum of a subarray from index a to b (inclusive).

Without a prefix sum array, calculating this would take O(b - a + 1) time, which can be up to O(n) for a large range.

With our (1-indexed) prefix sum array, the sum can be found using a simple formula:

sum(a, b) = prefix[b+1] - prefix[a]

Why it works: prefix[b+1] is the sum from 0 to b. prefix[a] is the sum from 0 to a-1. Subtracting the two leaves you with the sum from a to b.

2D Prefix Sums

The same technique can be extended to two dimensions to calculate the sum of any rectangular subgrid in a matrix in O(1) time after an O(n*m) preprocessing step. The formula relies on the principle of inclusion-exclusion.

sum(x1, y1, x2, y2) = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

Interactive Demos

Use the interactive simulations below to see how both 1D and 2D prefix sums are calculated and used to answer range queries instantly.