Are interval, segment, fenwick trees the same?

问题:

Today i listened a lecture about fenwick trees (binary indexed trees) and the teacher says than this tree is a generalization of interval and segment trees, but my implementations of this three data structures are different. Is this afirmation true? and Why?

回答1:

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.

回答2:

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.