Prefix Sum
Learn the Prefix Sum technique to answer range sum queries in O(1) time. Visualize how pre-computation transforms the array.
Prefix Sum: Range Queries
Learn the Prefix Sum technique to answer range sum queries in O(1) time. Visualize how pre-computation transforms the array.
Initialize sum = 0
Initialize sum = 0
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
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