I\'m interested in the first appearance in the CS literature of the data structu

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.