faiyaz26's blog

How to handle Multiple types of update in LAZY PROPAGATION ?
By faiyaz26, 12 years ago, In English

For this problem i have to do 3 kinds of update in Segment Tree. http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3867

To make it in time , i need to use Lazy Propagation. But how to handle all 3 update in lazy propagation ?

I have an idea to make 3 update function with 3 update lazy propagation array.

But when i am going to use query how i am supposed to know which update should be done first due to lazy propagation ?

Can anyone help me ?

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

»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Here you have just 2 different kind of updates: 1)add a linear function 2)set a linear function.

It is convenient to consider indexes of an array as point on X axis. Than you can transform each query to linear function in one of the form: x + d, -x + d or 0*x + d, where d in first two cases depends on index of the left most element of given range.

For each segment you need to maintain 3 value: 1) Sum of all elements, covered by current node. 2) Superposition of functions, which completely cover current node, but do not cover it's parent. Superposition of linear functions is a linear function. So if node covered by functions a*x+b and c*x + d you can assume that it is covered by single function (a+c)*x + (b+d). 3) Flag, whether all child's are covered by the same function (same flag as you would have used if you had just third type of queries).

So you only need to be careful when you are propagating flag (don't forget to propagate superposition of functions when you are propagating it).

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

    Ignore the comment

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

      more than 2 types of update queries like the problem mentioned in this link

      Or in this link, right?

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

      I don't agree with your statement : "Sorry.Didnt see it." Because you are trying this question since yesterday. And here is your unofficial account : hems1begi7 from which you are trying. This comment doesn't mean to hurt you, but I am really sorry if it hurts.

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

        And you made this account just so you can post this comment.

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

        How did you come to know the account you mentioned was his account?? why cant you comment with your own account? Please don't keep such useless comments. He did not ask whether you agree or not. P.S:This comment doesn't mean to hurt you, but I am really sorry if it hurts you. I just wanted to say these kind of comments are of no use to you also.

        → Reply