Блог пользователя jaguar1996

Прибавление на отрезке ДО
Автор jaguar1996, история, 8 лет назад, По-русски

Всем привет!

Столкнулся с задачей прибавления на отрезке и запроса минимума и суммы. Как вы уже догадались запутался с пушами)

Подскажите какой инвариант вы поддерживаете и если можно скиньте код вашего ДО. Интересует рекурсивная реализация)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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...

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Было-бы приятно, если-бы тут была ссылочка на задачку.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить