CODEWITHSUNDEEP
algorithmdata-structuresfenwick-tree
Luiguis
Luiguis

Reputation: 402

Are interval, segment, Fenwick trees the same?

Today I listened to a lecture about Fenwick trees (binary indexed trees (BIT)). While my implementations of these three data structures are different,
the teacher says that this tree is a generalization of interval and segment trees.

Is this affirmation true?
and Why?

Upvotes: 11

Views: 5154

Answers (2)

Peteris
Peteris

Reputation: 3756

The following classification seems sensible although different people are bound to mix these terms up.

Fenwick tree/Binary-indexed tree link

The one where you use a single array and operations on the binary representation to store prefix sums (also called cumulative sums). Elements can be members of a monoid.

Range tree link

The family of trees where each node represents a subrange of a given range, say [0, N]. Used to compute associative operations on intervals.

Interval tree link

Trees where you store actual intervals. Most commonly you take a midpoint, keep the intersecting intervals at the node and repeat the process for the intervals to the left and to the right of the point.

Segment tree link

Similar to a range tree where leaves are elementary intervals in a possibly continuous space rather than discrete and higher nodes are unions of the elementary intervals. Used to check for point inclusion.

Upvotes: 13

IVlad
IVlad

Reputation: 43487

I have never heard binary indexed trees called a generalization of anything. It's certainly not a generalization of interval trees and segment trees. I suggest you follow the links to convince yourself of this.

than this tree is a generalization of interval and segment trees

If by "this tree" your teacher meant "the binary indexed tree", then he is wrong.

but my implementations of this three data structures are different

Of course they are different, your teacher never said they shouldn't be. He just said one is a generalization of the other (which isn't true, but still). Either way, the implementations are supposed to be different.

What would have the same implementation is a binary indexed tree and a fenwick tree, because those are the same thing.

Upvotes: 5

Related Questions