Answer Range Sum Queries with Prefix Sums
Build prefix totals and compute sums for half-open index ranges.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Answer Range Sum Queries with Prefix Sums
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
This prefix list omits its leading zero. Run a sum for the half-open slice from index one to three. The printed six should make you question the subtraction. The broken program prints [3,2,6,8] and then six for range [1:3]. The actual slice contains negative one and four, whose sum is three. Without a leading zero, prefix positions no longer line up with Python's exclusive end index, and the subtraction uses the wrong pair. The list of values is three, negative one, four, two. The broken prefix array stores totals after positions zero through three: three, two, six, eight. The query subtracts the wrong entries and prints six for slice one to three.
- 00:44
Read that slice as Python does: include index one and two, exclude three. Its values are negative one and four, whose sum is three. Checking the slice directly catches the off-by-one formula. Think of each prefix entry as a boundary between elements. The boundary before the first element has total zero; the boundary after the first has total three. Omitting the first boundary shifts every later number one slot left and encourages a wrong subtraction. A direct sum of the requested small slice is a powerful oracle while developing the optimized version, even if production queries later avoid repeated slicing.
- 01:25
The diagnosis prints values [3,-1,4,2], prefix [0,3,2,6,8], and slice [-1,4]. Subtract prefix at start from prefix at end: six minus three gives three. The zero at position zero makes the formula work even when the requested range begins at the start. Define prefix[i] as the total of values strictly before position i. That definition forces prefix zero to equal zero. Prefix one is three, prefix two is two, prefix three is six, and prefix four is eight. To isolate indices one and two, subtract everything before index one from everything before index three: six minus three equals three.
- 02:09
This is a uniform half-open formula for a beginning, middle, or empty range. Try a range starting at zero to test the convention. For [0:2], the values are three and negative one, totaling two. The formula uses prefix two, which is two, minus prefix zero, which is zero. For [2:4], four plus two equals six, matching prefix four minus prefix two, or eight minus two. Both checks use the same half-open indexing rule as the original [1:3] query. The prefix totals in this example are zero, three, two, six, and eight. Notice that the sequence falls from three to two because the second value is
- 02:49
negative one. A prefix array is not necessarily sorted, so binary search on it would be unjustified. The range-sum formula still works: it subtracts accumulated totals at two boundaries and does not require those totals to increase. This matters when balances or temperature changes can be negative. The corrected builder appends a cumulative total after each number. For the same list it prints [0,3,2,6,8] and the query prints three. One preprocessing pass supports each later range sum with two indexing operations and one subtraction, as long as the source list stays unchanged.
- 03:31
The builder initializes an array containing zero. For each next source value, it adds that value to the last prefix total and appends the result. Four values therefore produce five prefix entries. A range-sum function checks the index order and boundaries before subtracting prefix[end] minus prefix[start]. The fixed run prints the five-entry list and then three. After one linear build, each query takes only two indexed reads and one subtraction. Precomputation is worthwhile when many queries reuse one unchanged list. The build costs one addition per element and stores one more number than the input length.
- 04:12
A single query on a one-off list may be simpler with sum(values[start:end]); the prefix method trades that upfront work and storage for constant-time repeated queries. That cost tradeoff is part of choosing the technique, not a property visible from one four-number demo. Split the full range into adjacent pieces as a consistency test. Range zero to two contains three and negative one, so its sum is two. Range two to four contains four and two, so its sum is six. Adding those answers gives eight, matching the full zero-to-four range. The middle prefix total cancels algebraically when the two differences are added.
- 04:53
This property can test many randomly chosen split points without hard-coding every expected answer. The verifier prints zero for an empty range and eight for the full list, then rejects an invalid range. Negative indices need explicit rejection because Python might otherwise interpret them from the end and return a believable wrong answer. Updating a source value makes later prefix totals stale. Suppose the second source value changes from negative one to five after the prefix array was built. The old prefix [0,3,2,6,8] would still answer the middle range as three, even though five plus four is nine.
- 05:35
Rebuilding gives [0,3,8,12,14], and prefix three minus prefix one now gives twelve minus three, or nine. This numerical update shows why the precomputed array belongs to one snapshot. If a workload changes values frequently, it may need a data structure designed for updates. For one query over a thousand numbers, a direct sum may be simpler than building another array. For a thousand queries over that same unchanged list, scanning each whole range could revisit many values, while one prefix build does roughly a thousand additions and each query reads two entries. The gain depends on query count and range length, so benchmark the actual workload.
- 06:19
If the list changes between queries, the cost of rebuilding can erase that advantage.
Understand the concept
A report asks many sums over portions of the same numeric list. Summing every slice works, but repeats work for every query. A prefix array stores the total before each index, so the sum over a half-open range from start to end is prefix[end] minus prefix[start].
If the prefix array starts at the first input value instead of a leading zero, empty ranges and ranges beginning at zero become awkward and off-by-one errors appear. Another common mistake treats end as inclusive while Python slicing treats it as exclusive.
Write the values and their prefix totals side by side. For [3, -1, 4, 2], the prefix list is [0, 3, 2, 6, 8]. The sum of positions one and two is prefix[3] minus prefix[1], or three. The initial zero makes the formula work uniformly when start is zero. Build prefix by starting with [0] and appending the last total plus each next value. A query validates 0 <= start <= end <= len(values), then subtracts two stored totals. This precomputation costs one pass; each later query uses constant-time indexing and subtraction.
An empty range where start equals end returns zero, and the full range uses the final prefix entry. The final run checks both, plus an invalid end index. Reject out-of-range queries rather than accidentally allowing Python's negative indexing to mask a caller's mistake. Prefix sums are appropriate when source values stay unchanged between queries. After a value changes, later prefix totals become stale and must be rebuilt or maintained with another data structure. Keep the half-open interval convention visible in function names and tests.
- A report asks many sums over portions of the same numeric list.
- If the prefix array starts at the first input value instead of a leading zero, empty ranges and ranges beginning at zero become awkward and off-by-one errors appear.
- Build prefix by starting with [0] and appending the last total plus each next value.
- An empty range where start equals end returns zero, and the full range uses the final prefix entry.
See it step by step
Read the code, predict the output, then compare it with the result.
01. Build the prefix totals
values=[3,-1,4,2]; prefix=[0]
for value in values: prefix.append(prefix[-1]+value)
print(prefix)
[0, 3, 2, 6, 8]The leading zero means prefix[i] always totals values before index i.
02. Subtract a half-open range
prefix=[0,3,2,6,8]
print(prefix[3]-prefix[1])
print(sum([3,-1,4,2][1:3]))
3
3Both calculations cover indices one and two, excluding endpoint three.
03. Test empty and full ranges
prefix=[0,3,2,6,8]
print(prefix[2]-prefix[2])
print(prefix[4]-prefix[0])
0
8Equal endpoints give zero; the full range uses the final stored total.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Observe the first result
A report asks many sums over portions of the same numeric list. Summing every slice works, but repeats work for every query. A prefix array stores the total before each index, so the sum over a half-open range from start to end is prefix[end] minus prefix[start].
The leading zero means prefix[i] always totals values before index i. Write the values and their prefix totals side by side. For [3, -1, 4, 2], the prefix list is [0, 3, 2, 6, 8]. The sum of positions one and two is prefix[3] minus prefix[1], or three. The initial zero makes the formula work uniformly when start is zero.
values=[3,-1,4,2]; prefix=[0]
for value in values: prefix.append(prefix[-1]+value)
print(prefix)
[0, 3, 2, 6, 8]- Predict the first sample's printed value and type.
- Run it, then compare with the expected output.
Change the rule deliberately
If the prefix array starts at the first input value instead of a leading zero, empty ranges and ranges beginning at zero become awkward and off-by-one errors appear. Another common mistake treats end as inclusive while Python slicing treats it as exclusive.
Both calculations cover indices one and two, excluding endpoint three. Build prefix by starting with [0] and appending the last total plus each next value. A query validates 0 <= start <= end <= len(values), then subtracts two stored totals. This precomputation costs one pass; each later query uses constant-time indexing and subtraction. Initialize totals = [0]. Validate 0 <= start <= end < len(prefix) before subtracting.
prefix=[0,3,2,6,8]
print(prefix[3]-prefix[1])
print(sum([3,-1,4,2][1:3]))
3
3- Identify the line that changes the rule.
- Run the corrected sample with the same input.
Verify the boundary
Write the values and their prefix totals side by side. For [3, -1, 4, 2], the prefix list is [0, 3, 2, 6, 8]. The sum of positions one and two is prefix[3] minus prefix[1], or three. The initial zero makes the formula work uniformly when start is zero. Build prefix by starting with [0] and appending the last total plus each next value. A query validates 0 <= start <= end <= len(values), then subtracts two stored totals. This precomputation costs one pass; each later query uses constant-time indexing and subtraction.
Equal endpoints give zero; the full range uses the final stored total. An empty range where start equals end returns zero, and the full range uses the final prefix entry. The final run checks both, plus an invalid end index. Reject out-of-range queries rather than accidentally allowing Python's negative indexing to mask a caller's mistake. Prefix sums are appropriate when source values stay unchanged between queries. After a value changes, later prefix totals become stale and must be rebuilt or maintained with another data structure. Keep the half-open interval convention visible in function names and tests.
prefix=[0,3,2,6,8]
print(prefix[2]-prefix[2])
print(prefix[4]-prefix[0])
0
8- Try the documented edge case.
- Explain why the output satisfies the function contract.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Initialize totals = [0]. Validate 0 <= start <= end < len(prefix) before subtracting.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
The visible failure
prefix = [values[0]]prefix = [0]; append(prefix[-1] + value) for each valueWhat happens: If the prefix array starts at the first input value instead of a leading zero, empty ranges and ranges beginning at zero become awkward and off-by-one errors appear.
Build prefix by starting with [0] and appending the last total plus each next value. A query validates 0 <= start <= end <= len(values), then subtracts two stored totals. This precomputation costs one pass; each later query uses constant-time indexing and subtraction.
Missing the edge condition
prefix[end+1] - prefix[start]prefix[end] - prefix[start] for [start,end)What happens: An empty range where start equals end returns zero, and the full range uses the final prefix entry.
Prefix sums are appropriate when source values stay unchanged between queries. After a value changes, later prefix totals become stale and must be rebuilt or maintained with another data structure. Keep the half-open interval convention visible in function names and tests.