Prefix Sums
Scenario
You have a log of daily website visitors for the past year. A product manager asks you 10,000 different questions like 'How many visitors between March 4 and August 12?'
Do you loop over the days and add them up every single time she asks, or can you precalculate something that answers any date range instantly?
Why it exists
Problem: Given an array, querying the sum of a subarray (from index i to j) takes O(n) time if you use a loop. If you need to answer q queries, the total time is O(q * n). For large arrays and many queries, this is too slow.
Naive approach: Run a `for` loop from index i to j and accumulate the sum every time a query is made.
Better idea: Spend O(n) time once to precompute a 'prefix sum' array, where each element at index k stores the sum of all elements from the start up to k. Then, any range sum from i to j can be found in O(1) time using subtraction: prefix[j] - prefix[i-1].
Mental model
It's like the odometer on a car. If the odometer reads 10,000 miles on Tuesday and 10,300 miles on Friday, you know you drove 300 miles in that window. You just subtracted the 'running totals'.
A prefix sum array simply keeps a running total. `prefix[i]` holds the sum of the original array elements from index 0 to index i. To find the sum of any slice [i..j], you take the running total up to j, and chop off the running total up to the part just before i (i-1). This reduces a loop over the array into a single O(1) subtraction.
Repeated decision: What is the running total up to this index? (previous prefix + current value)
Explanation
Prefix Sums trade O(n) space and O(n) upfront time for O(1) range queries.
Let's say your array is `[2, 4, 1, 5]`.
Your prefix sum array is built by adding the current element to the previous sum:
- prefix[0] = 2
- prefix[1] = 2 + 4 = 6
- prefix[2] = 6 + 1 = 7
- prefix[3] = 7 + 5 = 12
So the prefix array is `[2, 6, 7, 12]`.
Now, you want the sum of indices 1 through 3 (which is 4 + 1 + 5 = 10).
Instead of looping, you use the prefix array:
Take the total sum up to index 3 (which is 12). This includes index 0, which we don't want.
Subtract the sum up to index 0 (which is 2).
12 - 2 = 10.
You got the answer in O(1) time.
To avoid bounds checking issues when querying from index 0, it is extremely common to pad the prefix array with a leading zero. So the prefix array becomes `[0, 2, 6, 7, 12]`. Then the sum from i to j is simply `prefix[j+1] - prefix[i]`.
Key points
- O(1) Range Queries: After an O(n) precomputation step, any contiguous subarray sum can be found in constant time.
- Space-Time Tradeoff: We allocate O(n) extra space to store the prefix sums to save O(n) time on every query.
- Leading Zero: Constructing the prefix array of size n+1 with a leading 0 prevents out-of-bounds errors when querying a range that starts at index 0.
Pattern: Precomputation / Caching
Recognition cues:
- The problem asks for the sum of a subarray or contiguous range.
- You need to answer multiple queries on the same static array.
- The problem involves finding a subarray that sums to a specific target.
Failure signals
- You have a nested loop where the inner loop is just adding up numbers in a range.
- The input array is constantly changing (being updated). Prefix sums are for static arrays; if the array changes, updating the prefix array takes O(n). (Use a Segment Tree or Fenwick Tree instead).
Engineering examples
Financial Ledgers
Calculating the total revenue over arbitrary date ranges from daily sales data.
Daily data is static once recorded. A prefix sum table allows dashboards to load instantly regardless of the date range selected.
Image Processing (Integral Images)
Applying a blur filter requires computing the average color of a rectangle of pixels for every single pixel in the image.
A 2D prefix sum (integral image) allows finding the sum of any rectangle of pixels in O(1) time, dramatically speeding up rendering.
When not to use
- The array values are frequently updated: If you change `arr[0]`, you have to recalculate every single element in the prefix array, turning an O(1) update into an O(n) nightmare. Use a Fenwick Tree (Binary Indexed Tree) instead.
- You only need to calculate one range sum: If you only have one query, O(n) precomputation + O(1) query is the same as just doing an O(n) loop, but wastes O(n) space.
Common mistakes
- Off-by-one errors in indices: Without a leading zero in the prefix array, querying a range starting at index 0 requires a special `if i == 0` check. Using a 1-indexed prefix array (leading zero) is highly recommended.
- Integer overflow: If the array contains many large numbers, the running total can easily exceed the 32-bit integer limit in languages like Java or C++. Always use 64-bit integers (`long`) for prefix arrays if the data warrants it.
Glossary
- range queries
- Asking a question about a specific continuous section of data, like the total sum between two points.
- out-of-bounds errors
- Crashes that occur when trying to access a position in a list that doesn't exist.
- precomputation step
- Doing mathematical work ahead of time so the results can be used instantly later.
Recall questions
- What is the formula to find the sum of `arr[i...j]` using a prefix sum array (assuming no leading zero padding)?
- Why is it common practice to make the prefix sum array size n+1 with a leading 0?
- Why shouldn't you use a prefix sum array if the original array is frequently updated?
Questions & answers
Given an array of integers, find the 'pivot index' where the sum of all numbers strictly to the left equals the sum of all numbers strictly to the right.
Compute the total sum of the array first. Then iterate through, keeping a running 'left_sum'. The 'right_sum' is simply `total_sum - left_sum - arr[i]`. If they match, return i.
Approach: This is a space-optimized prefix sum problem.
Given an array and an integer k, find the total number of continuous subarrays whose sum equals to k.
Use a hash map to store the frequencies of all prefix sums seen so far. As you iterate, calculate the current prefix sum. If `current_sum - k` exists in the hash map, it means there is a valid subarray ending here.
Approach: Combining prefix sums with a hash map for O(n) lookup.
Interesting facts
- In 2D graphics and computer vision, a 2D prefix sum is called an 'Integral Image'. It was the secret sauce that allowed the Viola-Jones algorithm to do real-time facial recognition on early 2000s hardware by making box-blur and feature extraction O(1).
Continue learning
Previous: Arrays & Memory
Next: 2D Arrays & Matrices
Related: Arrays & Memory
Related: Hash Tables