jaguar1996's blog

Addition on a segment(Segment tree)
By jaguar1996, history, 8 years ago, translation, In English

Hi everybody!

I am solving problem that need addition on a segment and getting sum and minimum on a segment. I have some problem with lazy propagation.

Can you share your code with Segment tree. Preferably recursively)

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

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

Auto comment: topic has been translated by jaguar1996 (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

In every node of the segment tree put two values: sum of range and minimum of range.

Everytime you update a node with sum s and minimum x, update these values. If the range is [l, r], then s = s + (r - l + 1)·v (where v is the value you are adding to the range). Minimum should be updated too: x = x + v

Propagate the v value to the children as always.

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

    hello,i have a stupid question about segment tree lazy propagation..why we need to Propagate the v ((where v is the value you are adding to the range)value to its children when we do a update function, can not we Propagate the v value to the children when we do query function(or say it just do what we really want to do?) can you explain it more details,becasue it confused me sevearl days to think this question...thanks in advance...

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

      When applying lazy propagation, every node on the segment tree has some "lazy" values. In this case, the lazy values is the sum we are adding to a range.

      If you update a node that represents a range [l, r], you must update the lazy values of its children, but nothing more, there's no need to go down to the leaves of the tree. We use these lazy values to update the nodes when needed.

      So, when we attend another query, if we go to a node whose lazy value is on (it needs to be updated), we update the node and push the lazy value to the children (unless the node is a leaf)

      This way, the complexity of the queries will be O(logn)

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

Here's mine. It is only addition and minimum, but can be easily edited to support sum operation.

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

You can watch this video: https://www.youtube.com/watch?v=Tr-xEGoByFQ

I code a segment tree and talk about how lazy propagation works. I don't remember if I talk about sum, but it is not very complicated if you can get a good understanding of lazy propagation.

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

This problem is kind of similar. You can see the editorial and others code too.

→ Reply