A conceptual doubt about Segment Trees and Lazy Propagation.
Difference between en2 and en3, changed 0 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English sidchelseafan 2015-08-12 13:17:02 0 (published)
en2 English sidchelseafan 2015-08-12 13:16:32 4 Tiny change: 'lem:52C]. It is a si' -> 'lem:52C]. \n\nIt is a si'
en1 English sidchelseafan 2015-08-12 13:15:58 1134 Initial revision (saved to drafts)