the_algorithmic_eye's blog

By the_algorithmic_eye, 16 months ago,

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 :)

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 $[l \dots r]$.

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 $a[l] += k$. 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 range $[l \dots r]$? Can you decompose this range update as 2 suffix updates? It can be decomposed as such: if you need to increment the range $[l \dots r]$ 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 operations $a[l] += k$ and $a[r+1] -= k$ for each query and then take prefix sum of the array as before. A visual summary:

GIF

Code snippet

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 $a[l+i]$ 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 $[2 \dots 5]$ in the array $a = [0, 0, 0, 0, 0, 0]$ to get the array $[0, 0, 1, 2, 3, 4]$, what array would it have been before taking the prefix sum? It would have been $a = [0, 0, 1, 1, 1, 1]$. Performing $a[i] += a[i-1]$ 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 $[l \dots r]$. To do increasing range updates from this section, the range $[l \dots r]$ needs to be all $1$s, like $[0, 0, 0, 1, \dots 1, 0, 0]$. Let's think with the help of an example:

Say $a = [0, 0, 0, 0, 0, 0, 0, 0, 0]$ and we need to update the range $[3 \dots 6]$ to get $[0, 0, 0, 1, 2, 3, 4, 0, 0]$. Using section 1, we can get the array $a = [0, 0, 0, 1, 1, 1, 1, 0, 0]$. Try taking prefix sum over this and we get the array $a = [0, 0, 0, 1, 2, 3, 4, 4, 4]$. 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 operations $a[r+1] -= r-l+1$ 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 of $1$s, then we do the $a[r+1]$ subtraction for each query and then take prefix sum again.

Code snippet

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):

$dp[i+d] += dp[i], \forall d \in S$
TLE

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.

~AC

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.

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:

GIF

Code snippet

[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 $l, r \le 10^{9}$

Approach: For a moment, forget the large constraints of $l$ and $r$. How would you solve the problem when both are $\le 10^{6}$? Easy, just create a difference array representing cost without prime membership, of size $10^{6}$, range update using the given pairs, take prefix sum, then iterate over each day $i$ and take the sum of the minimum of ($cost_{i}, C$)

Code (smaller constraints)

We notice that there are at most $N$ pairs (~$10^{5}$). 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}$ and $b{i} + 1$, 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 the ids of those points instead. It's not very hard to recover the original distance between the uncompressed points.

Code

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.

Using map

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!

• +151

 » 16 months ago, # | ← Rev. 2 →   0 thanks for the blog.here is a problem for 1D range updates for adding AP to the range : https://cses.fi/problemset/task/1736
•  » » 16 months ago, # ^ |   0 I don't think it can be solved using concepts from this blog as it has range sum query too, in addition to range update.
 » 16 months ago, # |   +8 Wow! Keep your explaining styles! Very good, I like tutorials with animated videos!
•  » » 16 months ago, # ^ |   0 Thank you!
 » 16 months ago, # |   0 Great tutorial! And thanks for refer-up questions. Truly! Hats-off buddy
 » 16 months ago, # |   0 Special thanks for the enlisted problems :)
 » 16 months ago, # |   0 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 array a = [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]
•  » » 16 months ago, # ^ |   0 Fixed, thanks!
 » 16 months ago, # |   +8 I did cherry and bits! That GIF is awesome.
 » 16 months ago, # |   0 This blog is awesome it contains all the ranged query variation which is important and it gave a kind of revision to all of it. This is going into my list of best blogs. Thanks for making this stuff.
 » 16 months ago, # |   0 When you say AP it means AP with common difference = 1. What if the common difference is something other than 1?
•  » » 16 months ago, # ^ | ← Rev. 4 →   0 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: $a[l] += d, \quad a[r+1] -= d, \qquad a[r+1] -= (r-l+1) \times d$at the respective placesNow 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.
•  » » » 16 months ago, # ^ |   0 Yes got it, thanks for awesome explanation
•  » » » 12 months ago, # ^ |   0 I see you mentioned: Then taking prefix sum gives us [0,0,3,6,9,12,12,12]but we don't take prefix sum here. do we? After we get [0,0,3,3,3,3,0,0] we next proceed to make array as [0,0,3,3,3,3,-12,0].and after this, we take prefix sum again and make it as [0,0,3,6,9,12,0,0]Btw a very nice blog, and I think you can mention the "general A.P" case in the blog itself rather than in the comments.