eku's blog

My blog post on generalizing segment trees (reviews/opinions requested)
By eku, history, 5 years ago, In English

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.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by eku (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think that the text is well-written and quite easy to understand. Here are some comments:

  • Why do you use $$$O(\lg n)$$$ instead of $$$O(\log n)$$$?
  • It is not clear what "append c to a[i]" means in the CHAROCC example
  • "+ denotes array concatenation" — the symbol + is not a good choice here
  • What are first(u) and last(u)?

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).

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +7 Vote: I do not like it

    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 change have 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 add I 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 rewrite I 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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply