Prefix Sum Array
An integer array nums is given once, and it never changes. After that, many questions arrive. Each question names two indices, left and right, with left <= right, and asks for the total of the elements from index left to index right, both ends included. That total is the sum below.
nums[left] + nums[left + 1] + ... + nums[right]
Your class is NumArray. Its constructor, NumArray(nums), receives the array. Its method sumRange(left, right) answers one question and returns that total as an integer.
NumArray([-2, 0, 3, -5, 2, -1]) receives the array and returns null. sumRange(0, 2) is -2 + 0 + 3 = 1. sumRange(2, 5) is 3 + (-5) + 2 + (-1) = -1. sumRange(0, 5) is the whole array: -2 + 0 + 3 + (-5) + 2 + (-1) = -3.Prefix Sums
nums ➔ prefix with n + 1 slots, prefix[0] = 0 ➔ prefix[right + 1] - prefix[left]left..right. Or you need the running total at each position, counted from the start.| 1 | class NumArray: |
| 2 | """Range Sum Query - Immutable: build the prefix array once, then answer each range with one subtraction. |
| 3 | Time: O(N) to build, O(1) per sumRange | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | # prefix[i]: sum of the first i elements of nums; prefix[0] = 0, the sum of no elements |
| 8 | self.prefix = [0] * (len(nums) + 1) |
| 9 | # 1. Build The Prefix Array Once: |
| 10 | # Each next slot adds one more element to the previous running total, so prefix[i + 1] is always one element ahead of prefix[i]. |
| 11 | for i, num in enumerate(nums): |
| 12 | self.prefix[i + 1] = self.prefix[i] + num |
| 13 | |
| 14 | def sumRange(self, left: int, right: int) -> int: |
| 15 | # 1. Subtract The Two Running Totals: |
| 16 | # The first right + 1 elements are the first left elements followed by nums[left..right], so removing the first left elements' sum leaves exactly that range. |
| 17 | return self.prefix[right + 1] - self.prefix[left] |
self.prefix[i] is the sum of the first i elements, nums[0..i-1], for every i from 0 to n, so self.prefix[0] = 0.Build self.prefix once, with one more slot than nums has elements. self.prefix[0] = 0, and each next slot adds one element: self.prefix[i + 1] = self.prefix[i] + num. Then sumRange answers any range with one subtraction, self.prefix[right + 1] - self.prefix[left]. This is correct because the first right + 1 elements are the first left elements followed by nums[left..right]. Subtracting the sum of the first left elements leaves exactly the range. The leading 0 is the sum of no elements, so left = 0 uses the same formula with no special case. The trap is the index shift. self.prefix[i] stops just before nums[i], so the range ends at self.prefix[right + 1]. Writing self.prefix[right] leaves nums[right] out of every answer.
See it run
Prefix Sums, step by step
answers []
The top row is nums. The bottom row is prefix. A value of nums sits above the prefix slot it is added into, so nums[i] is above prefix[i + 1].
numthe value nums[i] that is added to the running totalprevthe earlier slot prefix[i] that the new slot builds onnewthe prefix slot that is written in this stepin rangea value of nums inside the range left..rightprefix[left]the total of the values before the rangeprefix[right + 1]the total of the values up to and including the rangetoo earlyprefix[right], which stops one value before the range ends
Start: nums has 6 values. prefix has 7 slots, one more than nums, and prefix[i] will be the sum of the first i values.
Gotcha 1 of 3
- The trap
Gotcha 1: Writing
self.prefix[right]instead ofself.prefix[right + 1]Mistakereturn self.prefix[right] - self.prefix[left]Fixreturn self.prefix[right + 1] - self.prefix[left]What happens:
self.prefix[i]is the sum of the elements before indexi. Soself.prefix[right]stops just beforenums[right]. The subtraction then returnsnums[left..right - 1], one element short. On a one-element range it returns 0.Example: nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2)Mistake: returns -2Fix: returns 1
- The target sum is given, and the ranges are unknown, as in Subarray Sum Equals K (LC 560). You must find or count the ranges that reach the sum. See Prefix Sum Map
- Each input adds a value to every element of a range, as in Corporate Flight Bookings (LC 1109). The ranges are written to, not read, and you return the final array. See Difference Array
- The array changes between the range questions, as in Range Sum Query - Mutable (LC 307): one
updatechanges every prefix total after it. See Fenwick Tree
Deep Dive
Why one subtraction gives any range
prefix[i] is the sum of the first i values, nums[0..i-1]. The first right + 1 values are the first left values followed by nums[left..right]. So prefix[right + 1] equals prefix[left] plus the sum of the range.
Move prefix[left] to the other side. The sum of the range is prefix[right + 1] - prefix[left]. This is one subtraction, however long the range is.
The extra slot prefix[0] = 0 is the sum of no values. A range that starts at index 0 has left = 0, and its formula is prefix[right + 1] - prefix[0]. No special case is needed.
The cost is O(N) to build prefix once and O(1) for every sumRange call. Without prefix, each call adds up to the whole range. With 10^4 values and 10^4 calls, that is up to 10^8 additions.
Building prefix and answering three queries
The input is nums = [-2, 0, 3, -5, 2, -1] from Range Sum Query - Immutable (LC 303). The build gives prefix = [0, -2, -2, 1, -4, -2, -3]. Each slot is the slot before it plus one value.
sumRange(0, 2) is prefix[3] - prefix[0] = 1 - 0 = 1. Check: -2 + 0 + 3 = 1.
sumRange(2, 5) is prefix[6] - prefix[2] = -3 - (-2) = -1. Check: 3 - 5 + 2 - 1 = -1.
sumRange(0, 5) is prefix[6] - prefix[0] = -3. These three answers match the examples of the problem.
The trap is the index shift. prefix[right] stops before nums[right]. For sumRange(0, 2) it gives prefix[2] - prefix[0] = -2, which is one value short.
Which operations work, and what the same array gives
The method needs an operation that can be undone. Subtraction undoes addition, so sums work. Counts work for the same reason. XOR is its own undo, so XOR works. In XOR Queries of a Subarray (LC 1310), arr = [1, 3, 4, 8] has the query answers [2, 7, 14, 8] for the ranges [0, 1], [1, 2], [0, 3] and [3, 3].
A maximum or a minimum cannot be undone. Once a larger value is in prefix, taking it out is impossible, so this method does not give the maximum of a range.
The array also answers questions about positions. In Find Pivot Index (LC 724), the sum left of index i is prefix[i], and the sum right of it is prefix[n] - prefix[i + 1]. For [1, 7, 3, 6, 5, 6] the two sums are equal at index 3.
For a grid, as in Range Sum Query 2D - Immutable (LC 304), prefix[r][c] holds the sum of the rectangle of the first r rows and the first c columns. The sum of a rectangle with corners (r1, c1) and (r2, c2) is prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1]. The last term adds back the corner that both subtractions removed.
60-Second Pitch
"The array does not change and there are many range questions, so I do the adding once. I build prefix with one extra slot, where prefix[0] is 0 and prefix[i + 1] is prefix[i] plus one value. Then prefix[i] is the sum of the first i values. A range from left to right is the first right + 1 values minus the first left values. So the answer is prefix[right + 1] - prefix[left], one subtraction. The build is O(N) time, each query is O(1), and the extra space is O(N). The extra slot removes the special case for left = 0."
Common Questions
- Why does
prefixhave one more slot thannums? prefix[0] = 0is the sum of no values. With it, a range that starts at index 0 uses the same formula as every other range. Without it,left = 0needs a special case or readsprefix[-1].- What is the cost of building and of querying?
The build costs
O(N)time andO(N)space. Each query is one subtraction, so it costsO(1). ForQqueries the total isO(N + Q), and the direct way costs up toO(N * Q).- Does it work for a maximum or a minimum?
No. The formula needs an operation that can be undone, and a maximum cannot be undone. Sums, counts and XOR can be undone. A range maximum needs a sparse table or a segment tree.
- What changes if the array can be updated between queries?
One update would change every slot after it, which costs
O(N). A Fenwick Tree keeps the same range sums withO(log N)for an update and for a query.- How do you extend it to a two-dimensional grid?
Store
prefix[r][c]as the sum of the firstrrows and firstccolumns. Build it withprefix[r + 1][c + 1] = M[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c]. A query adds the large rectangle, subtracts the two strips, and adds back the corner they both removed.
SWE Reasoning
Spot it
- The array does not change, and there are many questions about the sum, count or XOR of a range
left..right. - The operation can be undone: sum, count or XOR.
- A question needs the total to the left or to the right of each position (Find Pivot Index (LC 724)).
- Example problems: Range Sum Query - Immutable (LC 303), Range Sum Query 2D - Immutable (LC 304), XOR Queries of a Subarray (LC 1310).
The invariant, step by step
self.prefixhasn + 1slots, andself.prefix[0] = 0.- The build loop sets
self.prefix[i + 1] = self.prefix[i] + num. - So
self.prefix[i]is the sum ofnums[0..i-1]for everyi. - The first
right + 1values are the firstleftvalues followed by the range. - So
self.prefix[right + 1] - self.prefix[left]is exactly the sum ofnums[left..right].
Traps
- Reading
self.prefix[right]. The slot stops beforenums[right], and every answer is one value short. - Leaving out the leading 0. A range with
left = 0then needsself.prefix[left - 1], which isself.prefix[-1]in Python. It reads the last slot without an error and gives a wrong answer. - Adding up the range inside
sumRange. The answers are correct, but each call costs the length of the range. - Using the method on an array that changes. One
updatechanges every slot after it. The Fenwick Tree card handles that case.
Practice
Prefix Sum Array
An integer array nums is given once, and it never changes. After that, many questions arrive. Each question names two indices, left and right, with left <= right, and asks for the total of the elements from index left to index right, both ends included. That total is the sum below.
nums[left] + nums[left + 1] + ... + nums[right]
Your class is NumArray. Its constructor, NumArray(nums), receives the array. Its method sumRange(left, right) answers one question and returns that total as an integer.
NumArray([-2, 0, 3, -5, 2, -1]) receives the array and returns null. sumRange(0, 2) is -2 + 0 + 3 = 1. sumRange(2, 5) is 3 + (-5) + 2 + (-1) = -1. sumRange(0, 5) is the whole array: -2 + 0 + 3 + (-5) + 2 + (-1) = -3.Prefix Sums
nums ➔ prefix with n + 1 slots, prefix[0] = 0 ➔ prefix[right + 1] - prefix[left]left..right. Or you need the running total at each position, counted from the start.| 1 | class NumArray: |
| 2 | """Range Sum Query - Immutable: build the prefix array once, then answer each range with one subtraction. |
| 3 | Time: O(N) to build, O(1) per sumRange | Space: O(N) |
| 4 | """ |
| 5 | |
| 6 | def __init__(self, nums: list[int]) -> None: |
| 7 | # prefix[i]: sum of the first i elements of nums; prefix[0] = 0, the sum of no elements |
| 8 | self.prefix = [0] * (len(nums) + 1) |
| 9 | # 1. Build The Prefix Array Once: |
| 10 | # Each next slot adds one more element to the previous running total, so prefix[i + 1] is always one element ahead of prefix[i]. |
| 11 | for i, num in enumerate(nums): |
| 12 | self.prefix[i + 1] = self.prefix[i] + num |
| 13 | |
| 14 | def sumRange(self, left: int, right: int) -> int: |
| 15 | # 1. Subtract The Two Running Totals: |
| 16 | # The first right + 1 elements are the first left elements followed by nums[left..right], so removing the first left elements' sum leaves exactly that range. |
| 17 | return self.prefix[right + 1] - self.prefix[left] |
self.prefix[i] is the sum of the first i elements, nums[0..i-1], for every i from 0 to n, so self.prefix[0] = 0.Build self.prefix once, with one more slot than nums has elements. self.prefix[0] = 0, and each next slot adds one element: self.prefix[i + 1] = self.prefix[i] + num. Then sumRange answers any range with one subtraction, self.prefix[right + 1] - self.prefix[left]. This is correct because the first right + 1 elements are the first left elements followed by nums[left..right]. Subtracting the sum of the first left elements leaves exactly the range. The leading 0 is the sum of no elements, so left = 0 uses the same formula with no special case. The trap is the index shift. self.prefix[i] stops just before nums[i], so the range ends at self.prefix[right + 1]. Writing self.prefix[right] leaves nums[right] out of every answer.
See it run
Prefix Sums, step by step
answers []
The top row is nums. The bottom row is prefix. A value of nums sits above the prefix slot it is added into, so nums[i] is above prefix[i + 1].
numthe value nums[i] that is added to the running totalprevthe earlier slot prefix[i] that the new slot builds onnewthe prefix slot that is written in this stepin rangea value of nums inside the range left..rightprefix[left]the total of the values before the rangeprefix[right + 1]the total of the values up to and including the rangetoo earlyprefix[right], which stops one value before the range ends
Start: nums has 6 values. prefix has 7 slots, one more than nums, and prefix[i] will be the sum of the first i values.
Gotcha 1 of 3
- The trap
Gotcha 1: Writing
self.prefix[right]instead ofself.prefix[right + 1]Mistakereturn self.prefix[right] - self.prefix[left]Fixreturn self.prefix[right + 1] - self.prefix[left]What happens:
self.prefix[i]is the sum of the elements before indexi. Soself.prefix[right]stops just beforenums[right]. The subtraction then returnsnums[left..right - 1], one element short. On a one-element range it returns 0.Example: nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2)Mistake: returns -2Fix: returns 1
- The target sum is given, and the ranges are unknown, as in Subarray Sum Equals K (LC 560). You must find or count the ranges that reach the sum. See Prefix Sum Map
- Each input adds a value to every element of a range, as in Corporate Flight Bookings (LC 1109). The ranges are written to, not read, and you return the final array. See Difference Array
- The array changes between the range questions, as in Range Sum Query - Mutable (LC 307): one
updatechanges every prefix total after it. See Fenwick Tree
Deep Dive
Why one subtraction gives any range
prefix[i] is the sum of the first i values, nums[0..i-1]. The first right + 1 values are the first left values followed by nums[left..right]. So prefix[right + 1] equals prefix[left] plus the sum of the range.
Move prefix[left] to the other side. The sum of the range is prefix[right + 1] - prefix[left]. This is one subtraction, however long the range is.
The extra slot prefix[0] = 0 is the sum of no values. A range that starts at index 0 has left = 0, and its formula is prefix[right + 1] - prefix[0]. No special case is needed.
The cost is O(N) to build prefix once and O(1) for every sumRange call. Without prefix, each call adds up to the whole range. With 10^4 values and 10^4 calls, that is up to 10^8 additions.
Building prefix and answering three queries
The input is nums = [-2, 0, 3, -5, 2, -1] from Range Sum Query - Immutable (LC 303). The build gives prefix = [0, -2, -2, 1, -4, -2, -3]. Each slot is the slot before it plus one value.
sumRange(0, 2) is prefix[3] - prefix[0] = 1 - 0 = 1. Check: -2 + 0 + 3 = 1.
sumRange(2, 5) is prefix[6] - prefix[2] = -3 - (-2) = -1. Check: 3 - 5 + 2 - 1 = -1.
sumRange(0, 5) is prefix[6] - prefix[0] = -3. These three answers match the examples of the problem.
The trap is the index shift. prefix[right] stops before nums[right]. For sumRange(0, 2) it gives prefix[2] - prefix[0] = -2, which is one value short.
Which operations work, and what the same array gives
The method needs an operation that can be undone. Subtraction undoes addition, so sums work. Counts work for the same reason. XOR is its own undo, so XOR works. In XOR Queries of a Subarray (LC 1310), arr = [1, 3, 4, 8] has the query answers [2, 7, 14, 8] for the ranges [0, 1], [1, 2], [0, 3] and [3, 3].
A maximum or a minimum cannot be undone. Once a larger value is in prefix, taking it out is impossible, so this method does not give the maximum of a range.
The array also answers questions about positions. In Find Pivot Index (LC 724), the sum left of index i is prefix[i], and the sum right of it is prefix[n] - prefix[i + 1]. For [1, 7, 3, 6, 5, 6] the two sums are equal at index 3.
For a grid, as in Range Sum Query 2D - Immutable (LC 304), prefix[r][c] holds the sum of the rectangle of the first r rows and the first c columns. The sum of a rectangle with corners (r1, c1) and (r2, c2) is prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1]. The last term adds back the corner that both subtractions removed.
60-Second Pitch
"The array does not change and there are many range questions, so I do the adding once. I build prefix with one extra slot, where prefix[0] is 0 and prefix[i + 1] is prefix[i] plus one value. Then prefix[i] is the sum of the first i values. A range from left to right is the first right + 1 values minus the first left values. So the answer is prefix[right + 1] - prefix[left], one subtraction. The build is O(N) time, each query is O(1), and the extra space is O(N). The extra slot removes the special case for left = 0."
Common Questions
- Why does
prefixhave one more slot thannums? prefix[0] = 0is the sum of no values. With it, a range that starts at index 0 uses the same formula as every other range. Without it,left = 0needs a special case or readsprefix[-1].- What is the cost of building and of querying?
The build costs
O(N)time andO(N)space. Each query is one subtraction, so it costsO(1). ForQqueries the total isO(N + Q), and the direct way costs up toO(N * Q).- Does it work for a maximum or a minimum?
No. The formula needs an operation that can be undone, and a maximum cannot be undone. Sums, counts and XOR can be undone. A range maximum needs a sparse table or a segment tree.
- What changes if the array can be updated between queries?
One update would change every slot after it, which costs
O(N). A Fenwick Tree keeps the same range sums withO(log N)for an update and for a query.- How do you extend it to a two-dimensional grid?
Store
prefix[r][c]as the sum of the firstrrows and firstccolumns. Build it withprefix[r + 1][c + 1] = M[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c]. A query adds the large rectangle, subtracts the two strips, and adds back the corner they both removed.
SWE Reasoning
Spot it
- The array does not change, and there are many questions about the sum, count or XOR of a range
left..right. - The operation can be undone: sum, count or XOR.
- A question needs the total to the left or to the right of each position (Find Pivot Index (LC 724)).
- Example problems: Range Sum Query - Immutable (LC 303), Range Sum Query 2D - Immutable (LC 304), XOR Queries of a Subarray (LC 1310).
The invariant, step by step
self.prefixhasn + 1slots, andself.prefix[0] = 0.- The build loop sets
self.prefix[i + 1] = self.prefix[i] + num. - So
self.prefix[i]is the sum ofnums[0..i-1]for everyi. - The first
right + 1values are the firstleftvalues followed by the range. - So
self.prefix[right + 1] - self.prefix[left]is exactly the sum ofnums[left..right].
Traps
- Reading
self.prefix[right]. The slot stops beforenums[right], and every answer is one value short. - Leaving out the leading 0. A range with
left = 0then needsself.prefix[left - 1], which isself.prefix[-1]in Python. It reads the last slot without an error and gives a wrong answer. - Adding up the range inside
sumRange. The answers are correct, but each call costs the length of the range. - Using the method on an array that changes. One
updatechanges every slot after it. The Fenwick Tree card handles that case.