Fenwick tree vs Segment tree

Question

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.

Answer 1

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.

Answer 2

I found something on cp-Algorithm which might help you.

Segment tree -

• answers each query in O(logN)
• preprocessing done in O(N)
• Pros: good time complexity.
• Cons: larger amount of code compared to the other data structures.

Fenwick tree -

• answers each query in O(logN)

• preprocessing done in O(NlogN)

• Pros: the shortest code, good time complexity

• Cons: Fenwick tree can only be used for queries with L=1, so it is not applicable to many problems.