Archazey's blog

Lazy Update — Lazy mark
By Archazey, 10 years ago, In English

Hello,i have a question concerning lazy update.This question is generally for every lazy update use. When i mark some node with a flag,i don't actually update it,i just mark it.So a node with a mark on it isn't updated.

When I "go down" on some son and see that my node is marked,that's when I update it and give the mark to the sons.It seems more easier than me.This way i have to be sure that when I "go up" in my recursion and update my node with the value of the sons,the sons may not actually be updated,so I need to make sure they are.This takes more time,that's why I think this approach is slower than the other.

Here is my code for this problem http://www.codechef.com/viewsolution/5672423.

I also tried the other approach,when I mark a node and update it.It seems faster but not so pretty for me to implement. What is your version of implementing lazy update?Please let me know :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

In some problems involving segment tree and lazy update such as this you don't even need to have a boolean "flag". In other problems, instead, you must, but I prefer using that in a different way: if a node is flagged, then its value is updated, but its sons are not.

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

Your code looks good to me, I really didn't understand your question, these code doesn't work??

One detail saving memory, you don't need 8 times the size of the array, 4 is in off.

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

    My code works,but I think it is slower than the other approach(from my tests).I just want to learn the right way to code it and the faster,because lazy update is a slow process and every detail counts. I put 8*NMAX the size of the array because ,when I give the mark to the sons,I don't care if they're in my segment tree or not(left<=right).So sometimes I mark some useless nodes which may exceed 4*NMAX . From my tests ,putting the condition (left<=right) takes more time and makes it slower. When I have enough memory I let it 8*NMAX to speed up my lazy update. :)

    I also see that the other approach works with 4*NMAX memory,so that's another reason to implement it.

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

      If want to keep improving the speed, you may use bit operation in the code, but it really doesn´t affect the complexity... things like that...

      void query(int p, int b, int e)
{
     int mid = (b + e) >> 1;
     int left = p << 1;
     int right = left | 1;
}
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ohh,right,I forgot about that. Thanks :D

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

If you don't update the node itself when it has a lazy update mark, then if you query its ancestors before visiting it you won't get the correct answer, I believe. Consider you have a RSQ with all nodes equal to 0 and you add 5 to all the numbers in the range [1, 4]. If you then query [1, 8] before you update [1, 4], then [1, 8] won't be set as the sum of [1, 4] and [5, 8], and you will get 0, instead of the correct answer.

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

    You forgot one important aspect.When I mark a node,I update it's ancestors.And when I update it's ancestors,for every ancestor I call DOWN(leftson),DOWN(rightson),to make sure that they have the real values.So when I go up in my recursion from [1,4],I want to update [1,8].I call DOWN([1,4])(which it is 5),DOWN([5,8])(which is 0),and I'll have the right value for [1,8] :)

    The main difference is that ,for this approach,I need to call DOWN(leftson),DOWN(rightson),to make sure that theirs value is good updated(which takes more time,and more memory)

    So I think I'll move on to the other approach :)

    → Reply