_jairsaidds_'s blog

By _jairsaidds_, history, 2 years ago, In English,

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.

Read more »

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