### sidchelseafan's blog

By sidchelseafan, history, 7 years ago,

Hello everyone,

I have a conceptual doubt/problem about Segment Trees and Lazy Propagation in general. I was solving this problem, 52C - Circular RMQ.

It is a simple Range Minimum Query problem with range updates (Negative numbers are also present). And I submitted two solutions , One which doesn't involve Lazy Propagation and the other one which does. The first one got WA and the second one Ac'ed. I am curious. Have a look at the implementations.

Without Lazy Propagation — 12476539

With Lazy Propagation — 12477535

Isn't lazy propagation just a technique to do Range Updates Faster ? I had tried my first implementation on many Segment Tree based problems before and it had AC'ed.

The TL for this problem is 3s and its very liberal and hence I decided to code a normal Seg Tree without lazy propagation.

Link from where I got my Seg Tree

Don't both of them do Range updates in the same time O(log(n)) ? Can someone help me out. Thanks.

• 0

 » 7 years ago, # |   0 Auto comment: topic has been updated by sidchelseafan (previous revision, new revision, compare).
 » 7 years ago, # |   +1 The first code is just incorrect. If you don't do pushs(lazy porpagation) children nodes simply don't know anything about parents. Imagine the following situation:1 query : add some value to whole array. You will add value this to root node.2 query : find RMQ at interval [1;1]. You will go to leaf node and in leaf node you will get original value, but you won't take into account 1 modification query.To fix it you need to push modifier every time you want to go from some verticle to it's children. It's called lazy propogation.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Hey,Thanks for pointing my mistake out. I borrowed that code from the link I posted. Does that mean that code for Range Update is Wrong (From the link). Its the exact same code ? Q1.And another doubt, Would the same code(Without Lazy Propagation) work for Point Update as well?Q2. So Lazy propagation isn't just something you do for only Range update , you should also do it for Point Update ? Thanks (y)
•  » » » 7 years ago, # ^ |   +1 If you do point modification you add modifier only to leaf node, so you don't need to push it, so:1) Yes it will work2) You can do it, but push function will be never called.
•  » » » » 7 years ago, # ^ |   0 Thanks for your help. So, basically in lazy propagation, If i modify an interval, i should also modify the interval's sons/children. Which is precisely what my first code was not doing and hence I got WA. Am I correct ? Again, thanks for clearing this concept.
•  » » » » » 7 years ago, # ^ |   0 Yes, you are absolutely right