Lazy Propagation and it's general idea.

Revision en1, by _jairsaidds_, 2017-08-09 22:18:43

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?

Russian Tutorial about Lazy Propagation I guess.. For non Russian — Speakers...

Thanks in advance.

Tags segment tree, lazy propagation, data structure, russian

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English _jairsaidds_ 2017-08-09 22:26:47 146 Tiny change: 'gs, a set S, a binary' -> 'gs, a set \Chi, a binary'
en1 English _jairsaidds_ 2017-08-09 22:18:43 993 Initial revision (published)