algorithmtreesegment-treefenwick-tree

Fenwick tree vs Segment tree


I needed to compute sums within a range on an array, so I came across Segment Tree and Fenwick Tree and I noticed that both of these trees query and update with the same asymptotic running time. I did a bit more research, and these 2 data structures seem to do everything at the same speed. Both have linear memory usage (Segment Tree uses twice as much).

Aside from constant factors in running-time/memory and implementations, is there any reason why I would choose one over the other?

I am looking for an objective answer, like some operation that is faster with one than the other, or maybe some restriction one has that the other does not.

I saw 2 other StackOverflow questions about this, but the answers just described both data structures rather than explaining when one might be better than the other.


Solution

  • I read this on Quora. Hope you find it useful.

    1. 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 only because addition has an inverse operation. You cannot do this if the operation is non-invertible (such as max). On the other hand, every interval on a segment tree can be found as union of disjoint intervals and no inverse operation is required
    2. A BIT requires only half as much memory as a segment tree : In cases where you have masochistic memory constraints, you are almost stuck with using a BIT
    3. Though BIT and segment tree operations are both O(log(n)), the segment tree operations have a larger constant factor : This should not matter for most cases. But once again, if you have masochistic time constraints, you might want to switch from a segment tree to a BIT. The constant factor might become more of a problem if the BIT/Segment tree is multidimensional.