Prefix Sums

The Prefix Sum technique involves creating an auxiliary array where prefix[i] stores the sum of all elements from nums[0] to nums[i]. This allows us to calculate the sum of any subarray nums[i...j] in O(1) time.

1. Concept

Given an array nums = [1, 2, 3, 4]. The prefix sum array P would be [1, 3, 6, 10].

• P[0] = nums[0] = 1
• P[1] = nums[0] + nums[1] = 1 + 2 = 3
• P[2] = P[1] + nums[2] = 3 + 3 = 6
• P[3] = P[2] + nums[3] = 6 + 4 = 10

Formula: P[i] = P[i-1] + nums[i] (for i > 0)

2. Range Sum Query

To find the sum of subarray from index L to R: Sum(L, R) = P[R] - P[L-1]

(If L=0, Sum(0, R) = P[R])

Example

Calculate sum of nums[1...3] (which is 2 + 3 + 4 = 9). Using Prefix Sums: P[3] - P[0] = 10 - 1 = 9.

3. Interactive: Range Sum Calculator

Visualizing how pre-computation allows O(1) queries.

1. Array: [3, 1, 4, 1, 5, 9]
2. Prefix: [3, 4, 8, 9, 14, 23]
3. Query(2, 4): Sum(4, 1, 5) = 10.
   • Calculation: P[4] - P[1] = 14 - 4 = 10.

L: R:

Index

Nums

Prefix

Select range to see calculation.

4. Implementation

class NumArray {
  private int[] prefix;

  public NumArray(int[] nums) {
    prefix = new int[nums.length];
    if (nums.length == 0) return;

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

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

package main

type NumArray struct {
	prefix []int
}

func Constructor(nums []int) NumArray {
	if len(nums) == 0 {
		return NumArray{prefix: []int{}}
	}
	prefix := make([]int, len(nums))
	prefix[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		prefix[i] = prefix[i-1] + nums[i]
	}
	return NumArray{prefix: prefix}
}

func (this *NumArray) SumRange(left int, right int) int {
	if left == 0 {
		return this.prefix[right]
	}
	return this.prefix[right] - this.prefix[left-1]
}

---

5. Deep Dive Strategy Lab: Prefix Sums

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?