Prefix Sum

Interview guide for Prefix Sum with intuition, dry run, C++ code, complexity, and practice problems

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Prefix Sum.

1. Intuition

Prefix sum stores the total from the start up to each index. Then any range sum becomes:

sum(l..r) = prefix[r + 1] - prefix[l]

It exists because repeated range queries are too slow if you recompute each sum directly.

2. How It Works

Build a prefix array
Each position stores all values before it
Answer ranges by subtraction
Add a hash map if you need counts of prefix sums

3. Pattern Recognition

Think prefix sum when you see:

range sum queries
number of subarrays with target sum
balance of zeros and ones
cumulative score or frequency

4. Dry Run Example

Input:

nums = [3, 1, 4, 1, 5]
query = sum(1..3)

Step-by-step execution:

Prefix becomes [0, 3, 4, 8, 9, 14]
Range 1..3 means prefix[4] - prefix[1]
9 - 3 = 6

Final Output:

5. Code (C++)

vector<int> buildPrefix(const vector<int>& nums) {
  vector<int> prefix(nums.size() + 1, 0);

  for (int i = 0; i < static_cast<int>(nums.size()); i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }

  return prefix;
}

int rangeSum(const vector<int>& prefix, int left, int right) {
  return prefix[right + 1] - prefix[left];
}