Prefix Sum: The Ultimate Tool for Range Queries

Why Use Prefix Sum?

Brute force range sum: Every query requires O(n) traversal, leading to O(n²) total time for multiple queries.

Prefix sum preprocesses the array once in O(n), allowing every subsequent range query to be answered in O(1).

Core Logic:

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

Sum of range [l, r] = prefix[r+1] - prefix[l]

1D Prefix Sum

Template

int[] buildPrefix(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n + 1];   // Extra space to handle prefix[0] = 0
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// Query the sum of range [l, r] (0-indexed)
int query(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

{
  "type": "array-highlight",
  "title": "Building Prefix Sum for nums=[3,1,4,1,5,9]",
  "steps": [
    {
      "note": "Initial: prefix=[0, 0, 0, 0, 0, 0, 0], start at i=0",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 0, 0, 0, 0, 0, 0],
      "highlight": [0],
      "highlight2": [1]
    },
    {
      "note": "prefix[1] = prefix[0] + nums[0] = 0 + 3 = 3",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 0, 0, 0, 0, 0],
      "highlight": [0],
      "highlight2": [1]
    },
    {
      "note": "prefix[2] = prefix[1] + nums[1] = 3 + 1 = 4",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 0, 0, 0, 0],
      "highlight": [1],
      "highlight2": [2]
    },
    {
      "note": "prefix[3] = prefix[2] + nums[2] = 4 + 4 = 8",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 8, 0, 0, 0],
      "highlight": [2],
      "highlight2": [3]
    },
    {
      "note": "Done: prefix=[0,3,4,8,9,14,23]. Sum of [1,3] = prefix[4]-prefix[1] = 9-3 = 6",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 8, 9, 14, 23],
      "highlight": [1, 2, 3],
      "highlight2": [1, 4],
      "matched": [1, 2, 3]
    }
  ]
}

Range Sum Query - Immutable (LeetCode 303)

class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

Prefix Sum + Hash Map

When problems ask for "the number of subarrays whose sum is K," combine prefix sum with a Hash Map to store frequencies of previously seen prefix sums.

Key Observation: If prefix[j] - prefix[i] == k, then the sum of elements nums[i..j-1] is exactly k.

This simplifies to: Find how many indices i satisfy prefix[i] == currentSum - k.

Subarray Sum Equals K (LeetCode 560)

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);   // Represents an empty subarray with sum 0
    int sum = 0, res = 0;
    for (int num : nums) {
        sum += num;
        // Check if there's a prefix in the past such that CurrentSum - PastPrefix == k
        res += count.getOrDefault(sum - k, 0);
        count.merge(sum, 1, Integer::sum);
    }
    return res;
}

Contiguous Array (LeetCode 525)

Find the longest subarray with equal numbers of 0s and 1s. By mapping 0 to -1, the problem becomes "find the longest subarray with a sum of 0":

int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstSeen = new HashMap<>();
    firstSeen.put(0, -1);
    int sum = 0, res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0 ? -1 : 1);
        if (firstSeen.containsKey(sum)) {
            // Calculate distance since the first time this sum appeared
            res = Math.max(res, i - firstSeen.get(sum));
        } else {
            // Only record the earliest index (to maximize the length)
            firstSeen.put(sum, i);
        }
    }
    return res;
}

2D Prefix Sum

Extending prefix sum to matrices:

prefix[i][j] = Sum of rectangle from (0,0) to (i-1, j-1)

Sum of submatrix from (r1, c1) to (r2, c2):
  = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

2D Range Sum Query (LeetCode 304)

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i-1][j] + prefix[i][j-1]
                    - prefix[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] - prefix[r1][c2+1]
             - prefix[r2+1][c1] + prefix[r1][c1];
    }
}

Comparison