Prefix Sum
Software Engineer path · lesson 45 of 99Learn the Prefix Sum technique to answer range sum queries in O(1) time. Visualize how pre-computation transforms the array.
Up to 12 whole numbers from -99 to 99.
Indices; clamped to the array.
prefix[0] = 0: the sum of nothing.
- 1prefix[0] = 0
- 2for i in 0 .. n-1: prefix[i+1] = prefix[i] + a[i]
- 3sum(a[l..r]) = prefix[r+1] - prefix[l]
- Build additions
- 0 / 7
- Query operations
- 0 / 1
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Build the prefix array
For a = [3, 1, 4, 1, 5], fill in P where P[i] is the sum of the first i elements.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
0
P[0]
Test your knowledge
What is the time complexity of a Range Sum Query AFTER building the prefix sum array?
Write the code
Range Sum Query
class NumArray {
constructor(nums) {
// Initialize with prefix sums
}
sumRange(left, right) {
// O(1) return
}
}
function solve(nums, queries) {
const obj = new NumArray(nums);
return queries.map(q => obj.sumRange(q[0], q[1]));
}The short version
Think of a running total on a receipt. If you want to know how much you spent on items 5 through 10, you don't sum them up again. You just take the running total at item 10 and subtract the running total at item 4.
In more depth
Cumulative Knowledge
A Prefix Sum array stores the cumulative sum up to index i.
To find the sum of any subarray from index L to R, we don't need to loop. We just calculate:
Sum(L, R) = P[R] - P[L-1] (when L = 0, the sum is simply P[R], since there's no P[-1])
This turns O(N) queries into O(1) queries.
A note on the practice challenge below: it builds the prefix array with an extra leading zero — prefix[0] = 0, prefix[i+1] = P[i] — so the same formula becomes prefix[R+1] - prefix[L] and the L=0 case stops being special. Same idea, shifted by one; you'll see both conventions in the wild.
When to reach for this
- Range Sum Query (Immutable)
- Find number of subarrays with sum K
- Calculate equilibrium/pivot points
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required