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.
Auto comment: topic has been updated by eku (previous revision, new revision, compare).
I think that the text is well-written and quite easy to understand. Here are some comments:
Then, the text explains what monoids and endomorphisms are, but I don't see at the moment why they are useful concepts in this context (instead of using simple non-mathematical terms).
Thanks for the review!
There's no particular reason for using $$$O(\lg n)$$$ instead of $$$O(\log n)$$$. I think I did that out of habit. I think more people will recognize $$$O(\log n)$$$, so I
will changehave changed it.a[i] is a string and c is a character. So if a[i] is "car" and c is 't', then on appending c to a[i] we'll get "cart". This is similar to C++ string's push_back.
I'll addI have added this example so that it's easier to understand.Python's list and Java and C++ strings use + for concatenation. I can't think of a more appropriate symbol. Can you suggest something?
Every segment tree node corresponds to a segment of the input array. first(u) and last(u) are the indices of the first and last elements of that segment. I thought it would be obvious from the statement
value(u) = f(a[first(u)..last(u)]), but it looks like it's not.I'll rewriteI have rewritten it to make it clearer.I like the term 'monoid' because it succinctly and effectively captures what I want to convey, i.e. 'a set with an associative binary operator and an identity element'. I got rid of 'endomorphism', though.
Some years ago I saw this and this generalized segment tree implementations by indy256 and learned a lot from them. Maybe you'll find them interesting.