1.2 Prefix Sum — DSA Crash Course

Deep Dive: How Prefix Sum Eliminates Repeated Work

Beginner tip: A prefix sum is like a running total. Imagine counting money as you open envelopes left to right. After opening 5 envelopes, you know the total so far. To find the sum of envelopes 3-5, just subtract the total after envelope 2 from the total after envelope 5. No need to re-count.

The Range Query Problem

Without prefix sum, "sum of elements 2 to 5" requires scanning 4 elements each time:

arr = [2, 4, 1, 3, 5, 7, 2]

Query: sum(2..5)?  scan: 1+3+5+7 = 16  -> O(n) per query
Query: sum(0..3)?  scan: 2+4+1+3 = 10  -> O(n) per query
1000 queries on array of 10^6 = 10^9 operations -> TOO SLOW

With prefix sum, build once and answer any query in O(1):

arr    = [2, 4, 1, 3, 5, 7, 2]
prefix = [0, 2, 6, 7, 10, 15, 22, 24]
         ^-- prefix[0]=0 is the secret ingredient

sum(2..5) = prefix[6] - prefix[2] = 22 - 6 = 16   O(1)!
sum(0..3) = prefix[4] - prefix[0] = 10 - 0 = 10   O(1)!

The HashMap Combo -- "Subarray Sum = K" Walkthrough

nums = [1, 2, 3, -2, 5], k = 5. How many subarrays sum to 5?

Index:  0    1    2    3    4
Value:  1    2    3   -2    5
Prefix: 1    3    6    4    9
                                   seen = {0: 1}
i=0: prefix=1, need 1-5=-4, not in seen. seen={0:1, 1:1}. count=0
i=1: prefix=3, need 3-5=-2, not in seen. seen={0:1, 1:1, 3:1}. count=0
i=2: prefix=6, need 6-5=1,  1 IS in seen! count=1 (subarray [2,3])
     seen={0:1, 1:1, 3:1, 6:1}
i=3: prefix=4, need 4-5=-1, not in seen. count=1. seen adds 4:1
i=4: prefix=9, need 9-5=4,  4 IS in seen! count=2 (subarray [5] OR [3,-2,5])

Answer: 2 subarrays

Why {0: 1} matters: It handles subarrays starting at index 0. If prefix itself equals k, then prefix - k = 0, which must be in the map.

2D Prefix Sum -- The Inclusion-Exclusion Principle

To get sum of shaded rectangle, use four corners:

+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |##|##|  |     sum(r1,c1,r2,c2) =
+--+--+--+--+       prefix[r2+1][c2+1]
|  |##|##|  |       - prefix[r1][c2+1]     (remove top)
+--+--+--+--+       - prefix[r2+1][c1]     (remove left)
                     + prefix[r1][c1]       (add back double-removed corner)

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Prefix Sum

Why It Exists

Brute force problem: "What is the sum of elements from index i to j?" -> scan O(n) each time. With prefix sum: Precompute once O(n), then answer ANY range query in O(1).

The Core Insight

arr     = [2, 4, 1, 3, 5]
prefix  = [0, 2, 6, 7, 10, 15]   <- note: prefix[0] = 0 (important!)

sum(arr[1..3]) = prefix[4] - prefix[1] = 10 - 2 = 8

When to Reach for Prefix Sum

1. "Range sum" / "subarray sum" -> Classic prefix sum
2. "Number of subarrays with sum = K" -> Prefix sum + HashMap
3. "Balance / equal halves" -> Prefix sum where you transform +1/-1
4. "Product except self" -> Prefix product + suffix product
5. "2D range queries" -> 2D prefix sum (include-exclude formula)

The HashMap Combo (Most Important Variant)

When the problem says "subarray with sum = K":

Build prefix sum as you go
At each index, check: prefix[i] - K exists in HashMap?
If yes, there's a subarray summing to K ending here
This is O(n) time, O(n) space

Common Mistakes

Forgetting prefix[0] = 0 (the empty prefix). This is crucial for subarrays starting at index 0.
Off-by-one: sum(i..j) = prefix[j+1] - prefix[i], NOT prefix[j] - prefix[i]
For the HashMap variant: initialize {0: 1} to handle subarrays starting from index 0

Problems

#	Problem	Difficulty	Pattern	Status
1	Range Sum Query - Immutable	Easy	Basic prefix sum	[ ]
2	Subarray Sum Equals K	Medium	Prefix + HashMap	[ ]
3	Contiguous Array	Medium	Prefix + HashMap	[ ]
4	Product of Array Except Self	Medium	Prefix/Suffix product	[ ]
5	Range Sum Query 2D - Immutable	Medium	2D prefix sum	[ ]