the_algorithmic_eye's blog

By the_algorithmic_eye, 3 weeks ago,
Small note

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 $[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

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 $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

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

$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.

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:

GIF

Code snippet

Similar problems: To be added from comments

Feel free to suggest problems in the comments and I'll add them to the relevant section.

Big thanks to all the editorials of the problems I've referred to. I hope it was at least somewhat useful, even if it is for the collection of problems that will hopefully be added to each section.

Also, if there are any mistakes, feel free to suggest corrections. UPD: Thanks for the appreciation in comments and contribution!

• +143

 » 2 weeks 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
•  » » 2 weeks 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.
 » 2 weeks ago, # |   +8 Wow! Keep your explaining styles! Very good, I like tutorials with animated videos!
•  » » 9 days ago, # ^ |   0 Thank you!
 » 2 weeks ago, # |   0 Great tutorial! And thanks for refer-up questions. Truly! Hats-off buddy
 » 2 weeks ago, # |   0 Special thanks for the enlisted problems :)
 » 2 weeks 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]
•  » » 2 weeks ago, # ^ |   0 Fixed, thanks!
 » 10 days ago, # |   +8 I did cherry and bits! That GIF is awesome.
 » 10 days 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.
 » 9 days ago, # |   0 When you say AP it means AP with common difference = 1. What if the common difference is something other than 1?
•  » » 9 days 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.
•  » » » 8 days ago, # ^ |   0 Yes got it, thanks for awesome explanation