Range Update in Square Root Decomposition Technique

general
,
1

Please Can somebody suggest link to study range update in Sqrt Decomposition Technique?

There was a question in recent Oct challenge which could have been solved by sqrt technique too with range update.

Question
Link : https://www.codechef.com/OCT16/problems/BGQRS

EDIT : I know the basic SQRT Techniique just the range update part as when we update it block by block, the next query which requires us to traverse each element(all in 1 block) then what happens?
Thanks

1 Like
2

The exact idea depends on the problem, but the general idea is like this. Suppose you want to update a range [l, r]. You start from l and move to the right until you reach the end of the block. Then, you jump from block to block until you reach the block containing r. Finally, you move from your current position to r. This way, you travelled O(\sqrt{n}) times.

2 Likes
3

You can study from here
https://blog.anudeep2011.com/mos-algorithm/
But I don’t think you can apply that in the problem that you have mentioned (correct me if I’m wrong),I think Sqrt Decomposition works only if the queries are independent i.e. one query doesn’t affect the result of the other, and the order in which the queries are answered doesn’t matter, which is generally not the case in problems involving update queries. Sqrt Decomposition is just an ordering of the queries to be answered, so that the complexity is reduced. You’ll realize this once you’re done studying the technique.

1 Like
4

@hemath_1

Take a look at this link: https://discuss.codechef.com/questions/86038/bgqrs-unofficial-editorial
This is the solution for this question with sqrt technique.
I was trying to solve it with this reference but I was having problem with range update.

2 Likes
5

Learned something new today, thanks :slight_smile:

6

You can do the update using lazy propagation also. I solved it using that. This is my solution https://www.codechef.com/viewsolution/11822102

7

that’s Nice you learned, now can you please explain to me why the max size of the block was chosen to be 20?
or
In general how do we choose the max size?

8

I think the method presented by zscoder is wrong. When you update ‘l’ to ‘r’ you cant jump from block to block because you have to update original array by the new value from ‘l’ to ‘r’ otherwise future queries will give wrong answers. In point update also we update the original array by the “new value”. So by this correct method range update will have O(n) and not O(sqrt n). Am I wrong ? and is there some other optimized way of range updates in sqrt decomp. ?