A conceptual doubt about Segment Trees and Lazy Propagation.

Правка en1, от sidchelseafan, 2015-08-12 13:15:58

Hello everyone,

I have a conceptual doubt/problem about Segment Trees and Lazy Propagation in general. I was solving this problem, 52C - Циклические 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.

Теги segment trees, lazy propagation, data structures, range query

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sidchelseafan 2015-08-12 13:17:02 0 (published)
en2 Английский sidchelseafan 2015-08-12 13:16:32 4 Tiny change: 'lem:52C]. It is a si' -> 'lem:52C]. \n\nIt is a si'
en1 Английский sidchelseafan 2015-08-12 13:15:58 1134 Initial revision (saved to drafts)