I read this on Quora. Hope you find it useful. There are things that a segment tree can do but a BIT cannot : A BIT essentially works with cumulative quantities. When the cumulative quantity for interval [i..j] is required, it is found as the difference between cumulative quantities for [1…j] and [1…i-1]. This works … Read more
What is happening here is, if you have an array of n elements, then the segment tree will have a leaf node for each of these n entries. Thus, we have (n) leaf nodes, and also (n-1) internal nodes. Total number of nodes= n + (n-1) = 2n-1 Now, we know its a full binary … Read more
All these data structures are used for solving different problems: Segment tree stores intervals, and optimized for “which of these intervals contains a given point” queries. Interval tree stores intervals as well, but optimized for “which of these intervals overlap with a given interval” queries. It can also be used for point queries – similar … Read more