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
A:
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.
IVlad
2010-05-09 06:17:13
i saw the topcoder's article and many querys in BIT are similar of interval trees.
Luiguis
2010-05-09 16:29:08
They may be similar, but that doesn't mean you can say that one data structure derives from another. A node in the interval tree holds one half of the interval its parent node holds, while a node in a BIT holds an interval given by the binary representation of a number.
IVlad
2010-05-09 16:37:00