Overview
A prefix sum array stores, at position i, the total of the first i elements. The sum of any range [l, r] is then prefix[r + 1] − prefix[l]: two lookups instead of a loop. Building the array is O(n) once; every query afterwards is O(1).
The idea generalises beautifully. Combined with a hash map of previously seen prefix sums, it counts subarrays summing to k in one pass — even with negative numbers, where sliding windows fail. Run it backwards and you get the difference array, which applies many range updates in O(1) each.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Build prefix array | O(n) |
| Range sum query | O(1) |
| 2D build / query | O(m·n) / O(1) |
| Range update with difference array | O(1) each, O(n) to finalise |
Patterns to recognise
Many range queries, no updates
Use it for: Range sum query, pivot index.
Build once, answer each query in O(1).
Count subarrays with a property
Use it for: Sum equals k, sum divisible by k.
Keep a map from prefix value (or prefix mod k) to how often it has occurred.
Batch of range updates
Use it for: Booking systems, car pooling, flight bookings.
Mark boundaries in a difference array, then sweep once.
Code template
from collections import defaultdict
def subarray_sum(nums, k):
seen = defaultdict(int)
seen[0] = 1 # empty prefix
running = count = 0
for x in nums:
running += x
count += seen[running - k]
seen[running] += 1
return count
int subarraySum(const vector<int>& nums, int k) {
unordered_map<long long, int> seen{{0, 1}}; // empty prefix
long long running = 0;
int count = 0;
for (int x : nums) {
running += x;
auto it = seen.find(running - k);
if (it != seen.end()) count += it->second;
++seen[running];
}
return count;
}
Common mistakes
- Forgetting to seed the map with prefix 0 → 1 misses subarrays that start at index 0.
- Updating the map before querying it can count an empty subarray.
- Prefix sums overflow 32-bit integers on large inputs.
- If the array changes between queries, plain prefix sums go stale — use a Fenwick tree (see Range Queries).
Quick check
Three questions on Prefix Sums. Get all three right to earn +15 XP.
-
With prefix[0] = 0 and prefix[i] = sum of the first i elements, the sum of arr[l..r] (inclusive) is:
prefix[r + 1] covers indices 0..r; subtracting prefix[l] removes 0..l-1.
-
After O(n) preprocessing, each range-sum query costs:
One subtraction of two stored values.
-
Counting subarrays that sum to k in O(n) combines prefix sums with:
At each position, add the number of earlier prefixes equal to current - k.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Range Sum Query – ImmutableLeetCode Easy +20
- Find Pivot IndexLeetCode Easy +20
- Product of Array Except SelfLeetCode Medium +40
- Subarray Sum Equals KLeetCode Medium +40
- Continuous Subarray SumLeetCode Medium +40
- Range Sum Query 2D – ImmutableLeetCode Medium +40
- Car PoolingLeetCode Medium +40
Stuck on Prefix Sums?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor