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.