sidchelseafan's blog

A conceptual doubt about Segment Trees and Lazy Propagation.
By sidchelseafan, history, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sidchelseafan (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply