I wrote a blog post on generalizing segment trees:↵
[https://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html](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 monoids and update functions as composable endomorphisms. The blog post explains what these terms mean, why they are suitable abstractions 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) usefulfor othersinteresting?↵
↵
You can see the templated C++ code here: [https://gist.github.com/sharmaeklavya2/99ed35efbb639bbe7d7b46b89b74fea0](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.
[https://sharmaeklavya2.github.io/blog/generalizing-segment-trees.html](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
↵
Can I please get comments/reviews/opinions on it? Do you think it is (or can be slightly altered to make it) useful
↵
You can see the templated C++ code here: [https://gist.github.com/sharmaeklavya2/99ed35efbb639bbe7d7b46b89b74fea0](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.