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.
Auto comment: topic has been updated by sidchelseafan (previous revision, new revision, compare).
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.
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)
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 work
2) You can do it, but push function will be never called.
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.
Yes, you are absolutely right