Lazy Propagation and it's general idea.

Правка en2, от _jairsaidds_, 2017-08-09 22:26:47

I have read some papers that states, Segment Trees can be designed when you have three things: a set S, a binary operation that holds associativity and also an identity element that is, when we have an algebraic structure called Monoid.

But, then I found and amazing link, it's written in Russian and I bet there is gold over there, they generalize the idea, behind lazy propagation, the thing is that I'm not able to get the idea that they use, inserting a new operator instead of when using Lazy Propagation, and the fact it needs to hold the distributive property with the original operator .

Can you Russian-Speaker guys help me a little bit, on clarifying the following link a bit, or at least re-write the main ideas, so as we can improve our skills with Segment Trees?

Link: Russian Version

Link 2: Translated Version

Thanks in advance.

Теги segment tree, lazy propagation, data structure, russian

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский _jairsaidds_ 2017-08-09 22:26:47 146 Tiny change: 'gs, a set S, a binary' -> 'gs, a set \Chi, a binary'
en1 Английский _jairsaidds_ 2017-08-09 22:18:43 993 Initial revision (published)