I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times with the name segment tree (mostly in algorithmic competition sites), it seems that the same name is also used for this data structure which is quite different from the first one and has application in computational geometry.

I'd like to know who introduced the data structure described in the TopCoder tutorial and if another name was initially used as there seems to be a confusion between the two data structures that go by the same name.

It seems to me that the Segment tree in the Wikipedia article is exactly the same as the segment tree you're used to hear about.

Segment trees as used in programming competitions can be generalized as working over any data type which forms a Semigroup (that is, any data type over which some binary associative operation can be defined on). As a reference, I've been implementing them in Haskell, the source code can be found here.

In this particular case, you'd have to notice that the power set of a set forms a commutative monoid with union, and monoids are, in particular, semigroups. Hence, the particular case described in Wikipedia is a segment tree where the data type is an Interval, and the associative operation is the union operation!.

Segment trees are a form of binary trees. So to clarify your question, the data structures in both links are the same. They might be used in different ways or for different operations but they are in fact the same. I do not know who introduced the "segment tree" use of binary trees, but I hope this helps.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.