Hello everyone,↵
↵
↵
I have a conceptual doubt/problem about Segment Trees and Lazy Propagation in general. I was solving this problem,↵
[problem:52C]. ↵
↵
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 — [submission:12476539]↵
↵
With Lazy Propagation — [submission: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](http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html)↵
↵
Don't both of them do Range updates in the same time O(log(n)) ? Can someone help me out. Thanks.
↵
↵
I have a conceptual doubt/problem about Segment Trees and Lazy Propagation in general. I was solving this problem,↵
[problem:52C]. ↵
↵
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 — [submission:12476539]↵
↵
With Lazy Propagation — [submission: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](http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html)↵
↵
Don't both of them do Range updates in the same time O(log(n)) ? Can someone help me out. Thanks.
