My blog post on generalizing segment trees (reviews/opinions requested)

Revision en5, by eku, 2019-07-30 18:17:40

I wrote a blog post on generalizing segment trees: https://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html

It's about a method of generalizing segment trees by expressing query outputs as elements of a monoid and updates as functions. The blog post explains what a monoid is, why these abstractions are suitable and demonstrates concepts with examples.

Can I please get comments/reviews/opinions on it? Do you think it is (or can be slightly altered to make it) useful or interesting?

You can see the templated C++ code here: https://gist.github.com/sharmaeklavya2/99ed35efbb639bbe7d7b46b89b74fea0

The blog post turned out to be more detailed and theoretical than I was expecting. It's more concerned with mathematical and algorithmic aspects than the practicality of using it in contests. But I can change that if you think that would make it better.

Tags #segment tree, templates

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English eku 2019-07-30 18:17:40 154
en4 English eku 2019-07-30 00:52:24 25 minor changes: 'monoids' -> 'elements of a monoid', 'useful for others' -> 'useful or interesting'
en3 English eku 2019-07-30 00:38:34 230 (published)
en2 English eku 2019-07-30 00:26:24 253
en1 English eku 2019-07-30 00:22:01 817 Initial revision (saved to drafts)