Many range sums on one array
Some problems give you an array once and then ask for the sums of many ranges of it, sometimes hundreds of thousands of them. A sliding window can keep a range's sum up to date when the range moves one step at a time, by adding the value that enters and subtracting the one that leaves. Here the ranges come in any order, so there is nothing to slide. Let's take a small array:
Each question names two positions and asks for the sum of the values from the first to the second, both included. The sum from position 1 to position 2 is , and the sum from position 0 to position 3 is . A loop that adds up the values of the range answers any one question, and for a single question it is all you need.
The loop is too slow when there are many questions. Say the array has values and there are questions. One question can cover the whole array, so it costs up to additions, and questions cost up to . CSES Static Range Sum Queries, a contest version of this task, allows 200,000 values and 200,000 questions:
By the rule of thumb of about simple operations a second, that is 400 seconds of work against a one-second limit. Much of that work is repeated: the ranges overlap, and the loop adds the same values again for every question that covers them. To see how to avoid that, take the question about positions 1 to 2 again. Its answer is the sum of the first three values with the first value taken away:
A prefix sum is the sum of the first few values of an array: the first one, the first two, the first three, and so on. The sum of any range is one prefix sum minus a shorter one, so if we compute every prefix sum once and store them, each range sum takes a single subtraction, for a range of 2 values or of 200,000.
Build the prefix array and subtract two entries
We store the prefix sums in a second array called prefix, where prefix[i] is the sum of the first i values of nums. For [4, 2, 7, 1]:
prefix[3] = 13 is the sum of the three highlighted values, .Four values give five entries, because the array starts with prefix[0] = 0, the sum of no values. Each later entry is the one before it plus one more value, so a single pass over nums fills the array with one addition per value:
To answer a question, we subtract two entries. prefix[3] = 13 is the sum of positions 0, 1 and 2, and prefix[1] = 4 is position 0 alone, so is the sum of positions 1 and 2. In general, prefix[right] - prefix[left] is the sum of the first right values without the first left values, which leaves the values at positions left through right - 1.
In the figure, the entries of prefix sit on the boundaries between values: prefix[0] before the first value and prefix[4] after the last. A range is the stretch between two boundaries, so we name it by those two numbers and write it [left, right). The square bracket says that position left is included, and the round bracket says that the range stops just before position right. This is a half-open range, and the range we just summed is [1, 3).
Written this way, the two numbers that name a range are the two entries we read, with no or to remember, and the range holds right - left values. The whole array is [0, 4), which reads prefix[4] - prefix[0], or . That is the reason for the leading zero: a range that starts at position 0 uses the same subtraction as every other range. When left equals right, as in [2, 2), the range is empty and its sum is prefix[2] - prefix[2] = 0.
Worked example
Build the array and answer one question
The trace builds prefix for [4, 2, 7, 1] one entry at a time and then answers the range [1, 3). It also runs on two other inputs: a whole array that holds a negative value, and an empty range.
prefix[0] is zero because the first zero elements have sum zero.
Change the example input
Current result: 9
Pick any range and read its sum
In this widget the array is fixed and you choose the range. It is our array with two more values, 5 and 3, added at the end, so there are more ranges to try. As you move left and right, the shaded cells of nums are the range, and the two marked entries of prefix are the only numbers the answer reads, however many cells are shaded. The staircase underneath draws each prefix sum as a height, so a range sum is the rise from one step to another.
Answer every call from a stored prefix array
Here is the same task as a judge problem. The array arrives once, in a constructor, and the questions arrive as method calls:
You get an integer array nums once. Write a class NumArray whose constructor takes nums and whose method sumRange(left, right) returns the sum of nums[left] through nums[right], both ends included. The array never changes between calls.
Constraints
-
nums.length -
nums[i] -
leftrightnums.length - At most calls to
sumRange
Sample · Input
nums = [-2,0,3,-5,2,-1] sumRange(0, 2), sumRange(2, 5), sumRange(0, 5)
Output
1, -1, -3
In the sample, sumRange(2, 5) asks for . Two things differ from our small example. Some of the values are negative, which changes nothing: the subtraction removes the first left values whatever their signs are. And the problem's right is the last position inside the range, while ours was the position just after it. Positions left through right are the half-open range [left, right + 1), so the answer is prefix[right + 1] - prefix[left].
The constructor builds prefix once and keeps it, and sumRange reads two of its entries:
class NumArray:
def __init__(self, nums):
self.prefix = [0]
for value in nums:
self.prefix.append(self.prefix[-1] + value)
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
num_array = NumArray([-2, 0, 3, -5, 2, -1])
print(num_array.sumRange(0, 2))
print(num_array.sumRange(2, 5))
print(num_array.sumRange(0, 5))For the sample, prefix is [0, -2, -2, 1, -4, -2, -3], and sumRange(2, 5) returns prefix[6] - prefix[2], which is .
Cost of range sums
- Adding up each range in a loop
per question - A range can cover the whole array, so questions cost up to additions.
- Building the prefix array
, once - One addition per value, and numbers of extra memory.
- Each question after that
- Two reads and one subtraction, however long the range is.
So values and questions cost about steps. At this problem's limits of each, that is 20,000 steps in place of . At 200,000 of each, it is 400,000 steps in place of .
When prefix sums work
Prefix sums need two things. First, the array must stay fixed between questions. Changing one value changes every prefix entry after it, which can be all of them. When changes and questions alternate, a Fenwick tree handles each one in steps.
Second, the operation must be one you can undo, because the answer starts from a longer prefix and takes the shorter prefix back out. Subtraction undoes addition, so sums work. Counts work too, because a count is a sum of 1s: mark each value with 1 if it passes the test and 0 if it does not, and take prefix sums of the marks. To count even values in [4, 2, 7, 1], the marks are [1, 1, 0, 0] and their prefix sums are [0, 1, 2, 2, 2]. The range [1, 4) holds even value, the 2.
XOR works as well. Written ^ in code and in formulas, it compares two numbers bit by bit and sets each bit of the result where exactly one of them has a 1. XOR-ing in the same number twice cancels it, , so XOR-ing the shorter prefix into the longer one cancels the values they share and leaves the XOR of the range.
| Range question | What prefix holds | Answer for [left, right) |
|---|---|---|
| Sum | running sum | prefix[right] - prefix[left] |
| How many values pass a test | running count | prefix[right] - prefix[left] |
| XOR | running XOR | prefix[right] ^ prefix[left] |
| Minimum or maximum | running minimum or maximum | Not possible |
The last row fails the second condition. A minimum cannot be undone: the minimum of the first three values and the minimum of the first one do not determine the minimum of positions 1 and 2.
Deeper read: range minimums and prefix minimums
Compare the arrays [1, 7] and [1, 3]. In both, the minimum of the first value is 1 and the minimum of the first two values is 1, so their prefix minimums are identical. But the minimum of the range [1, 2) is 7 in one array and 3 in the other. No formula that reads only the prefix minimums can give both answers.
For range minimums on a fixed array we need a different table. A sparse table stores the minimum of every range whose length is a power of two and answers a question from two overlapping ranges in . The Range queries lesson builds it.
Combine a prefix and a suffix around each position
Multiplication looks as if it passes the second condition, since division undoes it. It does until a value is 0: every prefix product from that value onward is 0, and dividing by 0 is not defined. The next problem rules division out altogether:
You get an integer array nums. Return an array answer where answer[i] is the product of every element of nums except nums[i]. Do not use division, and run in time.
Constraints
-
nums.length -
nums[i] - Every
answer[i], and the product of any prefix or suffix ofnums, fits in a 32-bit integer
Sample 1 · Input
nums = [1,2,3,4]
Output
[24,12,8,6]
Sample 2 · Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]
In the first sample, leaving out the 3 gives . A separate loop for each position would multiply values times, about multiplications at .
Without division we cannot take nums[i] back out of the product of the whole array, so we build each answer from two products that never contained it. The values other than nums[i] split into two runs: the ones before position i and the ones after it. Multiplying the run before i gives a prefix product. The run after i is a suffix, the end of the array instead of its start, and multiplying it gives a suffix product. The answer is the two products multiplied together:
| Position | Value | Product before | Product after | Answer |
|---|---|---|---|---|
| 0 | 1 | 24 | ||
| 1 | 2 | 12 | ||
| 2 | 3 | 8 | ||
| 3 | 4 | 6 |
Position 0 has no values before it and position 3 has none after it. Both of those products are 1, because multiplying by 1 changes nothing, the way adding 0 changes nothing in a sum.
The code does not need a separate array for each column of the table. It first fills answer with the products before each position. Then it walks back from the right end, keeping the product of the values it has passed in one variable, after:
def product_except_self(nums):
n = len(nums)
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
after = 1
for i in range(n - 1, -1, -1):
answer[i] *= after
after *= nums[i]
return answer
print(product_except_self([1, 2, 3, 4]))
print(product_except_self([-1, 1, 0, -3, 3]))In the second loop, answer[i] is multiplied by after before after takes in nums[i], so no position is ever multiplied by its own value. A 0 in the array needs no special case, because nothing is divided. In the second sample, only position 2 leaves the 0 out, and its answer is
The first loop does one multiplication per position and the second does two, about in all, which is 300,000 at the largest input.
Count the subarrays that have a given sum
So far each question named a range and asked for its sum. The next problem goes the other way: it names a sum and asks how many ranges have it.
You get an integer array nums and an integer k. Return how many contiguous, nonempty subarrays of nums sum to exactly k.
Constraints
-
nums.length -
nums[i] -
k
Sample 1 · Input
nums = [1,1,1], k = 2
Output
2
Sample 2 · Input
nums = [1,2,3], k = 3
Output
2
In the first sample the two subarrays are the first two 1s and the last two 1s. In the second they are [1, 2] and [3].
A subarray is a run of consecutive values, what this lesson has called a range so far. With a prefix array the sum of any one subarray is a single subtraction, so we could test them all. But an array of values has subarrays, and at that is 200,010,000 subtractions, twice the budget for a second. A sliding window is no help either. It shrinks the window from the left while the sum is above , and that is correct only when dropping a value lowers the sum. Here values can be negative, and dropping a raises the sum.
Instead, we go through the array once and, at each position, count the subarrays that end there. Suppose the scan has just read a value, and total is the sum of everything read so far, which is a prefix sum. A subarray that ends here is what remains when a shorter prefix is taken away, and it sums to when the two prefix sums differ by :
So the number of subarrays that end here and sum to is the number of shorter prefixes whose sum is total - k. To look that number up without searching, we keep a frequency map, a hash map from each prefix sum to how many times it has occurred so far. The map starts with the entry 0 → 1, for the empty prefix, whose sum is 0.
Here is the scan on the second sample, [1, 2, 3] with :
| Value read | total | total - k | Shorter prefixes with that sum | count |
|---|---|---|---|---|
| 1 | 1 | none | 0 | |
| 2 | 3 | 0 | one, the empty prefix | 1 |
| 3 | 6 | 3 | one, the prefix [1, 2] | 2 |
In the second row, total - k is 0, and the only prefix so far with sum 0 is the empty one the map started with. Taking the empty prefix away leaves [1, 2], a subarray that starts at position 0. Every subarray that starts at position 0 is found through that entry, so a map that starts empty misses all of them. In the third row, total - k is 3, the sum of the prefix [1, 2], and taking that prefix away leaves [3].
def subarray_sum(nums, k):
seen = {0: 1}
total = 0
count = 0
for x in nums:
total += x
count += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([1, 2, 3], 3))Each step looks up total - k before it stores total, so the map holds only prefixes that end earlier. With the lookup and the store swapped, a step could find the total it has just stored. That pairs a prefix with itself and counts a subarray with no values in it. This happens when , since total - k is then total itself: on [1, 2, 3] with the swapped version returns 3, and the answer is 0.
The scan does one lookup and one update per value, about 40,000 map operations at , where testing every subarray took 200,010,000 subtractions.
Group prefix sums by their remainder
Change one condition in the last problem and the same scan still works. This problem counts the subarrays whose sum is a multiple of , where the last one wanted the sum to equal :
You get an integer array nums and an integer k. Return how many contiguous, nonempty subarrays have a sum divisible by k.
Constraints
-
nums.length -
nums[i] -
k
Sample 1 · Input
nums = [4,5,0,-2,-3,1], k = 5
Output
7
Sample 2 · Input
nums = [5], k = 9
Output
0
A subarray sum is the difference of two prefix sums, so we need to know when a difference is a multiple of . It is a multiple exactly when the two numbers leave the same remainder on division by .
Take . Division by 5 splits a number into a multiple of 5 plus a remainder from 0 to 4: , and . When you subtract two numbers, you subtract their multiples of 5 and their remainders separately. The multiples always leave a multiple of 5, so the remainders decide whether the whole difference is one.
For the remainders are both 4 and cancel, and the difference, 5, is a multiple of 5. For the remainders leave , so the difference is 2 and not a multiple of 5. In general, two remainders from 0 to 4 differ by at most 4 either way, and the only multiple of 5 from to 4 is 0. So the difference of two numbers is a multiple of 5 exactly when their remainders are equal.
The counting scan stays the same, with the map keyed by total % k in place of total: at each step it looks up how many shorter prefixes have the same remainder as the current one. Here are the prefix sums of the first sample, starting with the empty prefix, and their remainders for :
prefix sum 0 4 9 9 7 4 5remainder 0 4 4 4 2 4 0Reading the remainders from left to right, the second 4 matches one earlier 4, the third matches two and the fourth matches three, and the final 0 matches the 0 the map started with:
A remainder is always one of 0 to , so an array of counters does the job of the map:
def subarrays_div_by_k(nums, k):
seen = [0] * k
seen[0] = 1
total = 0
count = 0
for x in nums:
total += x
r = total % k
count += seen[r]
seen[r] += 1
return count
print(subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5))
print(subarrays_div_by_k([5], 9))A prefix sum can be negative here, and Python's % still returns a remainder from 0 to for it: -2 % 5 is 3. So total % k is always a valid index, and two prefix sums that differ by a multiple of always get the same one.
Common prefix-sum mistakes
Building
prefixwithout the leading 0.- Where it breaks
- With
prefix = [4, 6, 13, 14], the sum of positionsleftthroughrightisprefix[right] - prefix[left - 1], and a range that starts at position 0 has no entry before it. For positions 0 and 1 the code readsprefix[1] - prefix[-1], which is outside the vector in C++. Python reads index as the last entry and gets , where the sum is 6. - The fix
- Start with 0, so that
prefixhas entries andprefix[0]is the sum of no values.
Using an inclusive right end as the half-open one.
- Where it breaks
- For positions 1 through 3 of
[4, 2, 7, 1],prefix[3] - prefix[1]is , which leaves out position 3. The sum is 10. - The fix
- When a problem's
rightis the last position inside the range, readprefix[right + 1] - prefix[left].
Starting the map of prefix sums empty.
- Where it breaks
- On
[1, 1, 1]with the count is 1 where the answer is 2. The subarray made of the first two 1s starts at position 0, and the prefix before it is the empty one. - The fix
- Start the map with
0 → 1, the empty prefix.
Keeping the prefix sums seen so far in a set, which records whether each one occurred but not how often.
- Where it breaks
- On
[0, 0]with the prefix sums are 0, 0 and 0. The second 0 has one earlier match and the third has two, so 3 subarrays sum to 0. A set finds one match at each step and answers 2. - The fix
- Store a count for each prefix sum and add the count.
Recall An array has `prefix = [0, 3, 8, 6, 10]`. What is the sum of positions 1 through 3, and what are the four values?
Positions 1 through 3 are the half-open range [1, 4), so the sum is prefix[4] - prefix[1], which is . Each value is the difference between two neighbouring entries of prefix: , , and give [3, 5, -2, 4], and .
Recall Run the counting scan on `[3, 4, -4, 3]` with $k = 3$. What does it return, and which step counts two subarrays at once?
The values of total are 3, 7, 3 and 6. The first step looks up 0 and finds the empty prefix, which counts [3]. The second looks up 4 and finds nothing. The third looks up 0 again and counts [3, 4, -4]. By the last step the map holds the prefix sum 3 twice, so looking up counts two subarrays at once, [4, -4, 3] and the final [3]. The scan returns 4.