Small note (was in spoiler but spoiler broke): Many might say this is too trivial a topic to write a blog about but a google search only links to some blogs where people are asking for the concept, rather than some written tutorial with problems(e.g 1, 2). This blog by arujbansal is an exception, but it only has the vanilla 1D version. Hopefully, this current blog can become a good collection of a variety of problems using this technique.
The general flow of the blog would be, first sharing a link to the problem that inspires the concept that follows. You may want to try the problem yourself first. Then I'll try explaining the concept and you can try submitting to get an AC if you want. Let's get started :)
1D range updates for adding a constant to the range
Motivating problem: Array Manipulation
Problem Summary: We are given an array and multiple queries asking us to add a constant value to all elements in the range
Unable to parse markup [type=CF_MATHJAX]
.Approach: Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index $$$l$$$, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, i.e
Unable to parse markup [type=CF_MATHJAX]
. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the rangeUnable to parse markup [type=CF_MATHJAX]
? Can you decompose this range update as 2 suffix updates? It can be decomposed as such: if you need to increment the rangeUnable to parse markup [type=CF_MATHJAX]
by $$$k$$$, you can increment the suffix starting at index $$$l$$$ by $$$k$$$ and decrement the suffix starting at index $$$r+1$$$ by $$$k$$$, i.e perform the operationsUnable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
for each query and then take prefix sum of the array as before. A visual summary:Similar problems: A. Greg and Array, B. Karen and Coffee, Maximum sum across all permutations (my old edi) (similar: C. Little Girl and maximum sum), D2. Encrypting Messages
1D range updates for adding an AP to the range
Motivating problem: Angry Cyborg
Problem Summary: A small variation to the previous problem. This time we need to add $$$1$$$ to $$$l$$$, $$$2$$$ to $$$l+1$$$, and so on. In general, we need to add $$$i+1$$$ to
Unable to parse markup [type=CF_MATHJAX]
for each query.Approach: How possibly we could add increasing values to the range? Just incrementing the first index by something won't help because while taking prefix sum, the same constant gets propagated for the whole range.
As before, how to increment a suffix? If we try to reverse-engineer the thought process, what array, after taking its prefix sum could give us an increasing sequence? For example, if we wish to update the range
Unable to parse markup [type=CF_MATHJAX]
in the arrayUnable to parse markup [type=CF_MATHJAX]
to get the arrayUnable to parse markup [type=CF_MATHJAX]
, what array would it have been before taking the prefix sum? It would have beenUnable to parse markup [type=CF_MATHJAX]
. PerformingUnable to parse markup [type=CF_MATHJAX]
on this array will give us the desired array. Now how to get an array with some suffix with the value $$$1$$$? Easy, just use the suffix update from section 1!Now let's think about a general range
Unable to parse markup [type=CF_MATHJAX]
. To do increasing range updates from this section, the rangeUnable to parse markup [type=CF_MATHJAX]
needs to be allUnable to parse markup [type=CF_MATHJAX]
. Let's think with the help of an example:Say
Unable to parse markup [type=CF_MATHJAX]
and we need to update the rangeUnable to parse markup [type=CF_MATHJAX]
to getUnable to parse markup [type=CF_MATHJAX]
. Using section 1, we can get the arrayUnable to parse markup [type=CF_MATHJAX]
. Try taking prefix sum over this and we get the arrayUnable to parse markup [type=CF_MATHJAX]
. As you can see, the last 2 indices too got incremented by $$$4$$$. We can decrement the index $$$7$$$ by $$$4$$$ in order for the $$$4$$$ to avoid being propagated towards the end of the array. Formally, perform the operationsUnable to parse markup [type=CF_MATHJAX]
for each query before taking the prefix sum for the whole array. So, in summary, we take prefix sum twice, first when we want to get the arrays ofUnable to parse markup [type=CF_MATHJAX]
subtraction for each query and then take prefix sum again.Similar problems: To be added from comments
DP + 1D range update
Motivating problem: Leaping Tak
Problem Summary: Find the number of ways to reach cell $$$N$$$ from cell $$$1$$$, by making a jump of $$$d$$$, where $$$d$$$ is any value that belongs to the union of the given ranges.
Approach: Let's discuss the brute force first, i.e. without range update optimisation. We define $$$dp[i]$$$ to be the number of ways to reach cell $$$i$$$. Finally, we want $$$dp[n]$$$. If you're a little familiar with DP problems, it is easy to come up with the following recurrence relation(let's ignore the modulo for now for simplicity):
Unable to parse markup [type=CF_MATHJAX]
You can notice that the above code is just doing range increments for several ranges with the value $$$dp[i]$$$, so we can use what we have learnt till now.
Note that we must take the prefix sum continuously rather than towards the end because, for $$$i$$$, $$$dp[i]$$$ must be the true value since we're adding it in the range update. Also, don't forget taking modulus if you're submitting for an AC.
Similar problems: To be added from comments
2D range update
Motivating problem: Cherry and Bits
(Modified) Problem Summary: We are given a 2D matrix with multiple queries. Each query gives us a rectangle which we need to increment by a constant (the bit will just depend on whether the sum is even or odd). This is same as the 1st section, except for the 2D case
Approach:
The editorial for this problem is nice, it perhaps explains in a better way than I could here. You can read about the approach from there. Nevertheless, a visual summary:
Similar problems: To be added from comments
[UPD: New section]
Range update with coordinate compression
Motivating problem: Snuke prime
Problem summary: Range update similar to section 1, but with large ranges, i.e
Unable to parse markup [type=CF_MATHJAX]
Approach: For a moment, forget the large constraints of $$$l$$$ and $$$r$$$. How would you solve the problem when both are
Unable to parse markup [type=CF_MATHJAX]
? Easy, just create a difference array representing cost without prime membership, of sizeUnable to parse markup [type=CF_MATHJAX]
, range update using the given pairs, take prefix sum, then iterate over each day $$$i$$$ and take the sum of the minimum of (Unable to parse markup [type=CF_MATHJAX]
)We notice that there are at most $$$N$$$ pairs (~
Unable to parse markup [type=CF_MATHJAX]
). So we can coordinate-compress the coordinates of the pairs and then do range update similar to section 1 on the compressed points. The editorial is very well-written and detailed but in short: we notice that only points where meaningful changes take place are $$$a_{i}$$$ andUnable to parse markup [type=CF_MATHJAX]
, similar to $$$l$$$ and $$$r+1$$$. We put them in a set and then assign an id to each point according to its order in the set (coordinate compression). Now we range update an array corresponding to these compressed points. Drawing analogy to section 1, whenever you want to do range update from $$$a_{i}$$$ to $$$b_{i}$$$, use theids of those points instead. It's not very hard to recover the original distance between the uncompressed points. It is also possible to shorten this code by directly using a map. i.e building a difference map instead of a difference array. The key will be the actual uncompressed point and its value will be the value corresponding to the difference array value as above. The difference between 2 keys will be the actual distance between the points.
Feel free to suggest problems in the comments and I'll add them to the relevant section.
UPD: Thanks for the appreciation/feedback in comments and contribution!
UPD: Check out this cool blog by peltorator on an advanced version of the same topic. He has added a bunch of generalizations for the updates. And just like me, he makes helpful visualizations using manim too!
Wow! Keep your explaining styles! Very good, I like tutorials with animated videos!
Special thanks for the enlisted problems :)
small mistake in 1D range updates for adding an AP to the range.
a = [0, 0, 0, 1, 1, 1, 1, 0, 0]Try taking prefix sum over this and we get the arraya = [0, 0, 0, 1, 2, 3, 4, 5, 6]. As you can see, the last 2 indices too got incremented by 5 and 6.it should be 4 and 4.
a = [0, 0, 0, 1, 2, 3, 4, 4, 4]I did cherry and bits! That GIF is awesome.
When you say AP it means AP with common difference = 1. What if the common difference is something other than 1?
I think the logic from the blog can be easily extended for a general A.P i.e $$$T_{n} = a + (n-1) \times d$$$
Let's say we want to increase the range $$$[2 \dots 5]$$$ in the array $$$[0, 0, 0, 0, 0, 0, 0, 0]$$$ by the AP having common difference $$$3$$$. Then instead of the 1st increment as range update of $$$1$$$, we do it as range update of $$$3$$$ to get $$$[0, 0, 3, 3, 3, 3, 0, 0]$$$. Then taking prefix sum gives us $$$[0, 0, 3, 6, 9, 12, 12, 12]$$$. Now subtract $$$12$$$ from the suffix starting at index $$$6$$$ and take prefix sum. In summary, modify the operations as follows:
at the respective places
Now if you also want the starting point (i.e $$$a$$$) to differ, something like AP having 1st term $$$2$$$ and a common difference of $$$3$$$, similar to $$$[0, 0, 2, 5, 8, 11, 0, 0]$$$, then perform a range decrement of $$$1$$$, after you get the final array using the logic above. More generally, perform a range increment of $$$a-d$$$ (which can be negative) on the array obtained from above.
Yes got it, thanks for awesome explanation
thanku so muchh