BIT Tree doubt

Can some one please suggest me some situations or usecases where we must opt BIT Tree and when to use segment Tree ? Also , please tell me why did they choose BIT Tree instead of using Segment tree in https://www.geeksforgeeks.org/number-of-elements-greater-than-k-in-the-range-l-to-r-using-fenwick-tree-offline-queries/ problem

2 Likes

Here’s a link to help you learn more about Seg. trees and BITs. If you can solve a problem using BITs, you can solve it with Seg. trees as well. The time complexities for both are the same, but BITs are a tad bit quicker. Problem is, Seg. trees can do things that BITs can’t. In competitive coding I guess, you may solve most of such questions with Seg. trees alone. :blush:

1 Like

Yes , it is true Segtree is more powerful than BIT but when to use them is tricky , you can’t use BIT everywhere as you can use segtree , there is one more condition that should always satisfy to implement BIT whereas not required in segtree that is , the operation must be reversible function , like we can do sum range , not range gcd . Also BIT is easier and faster , also faster to implement than segtree , it takes O(n) space .

1 Like

Here’s a really fast implementation of SegTree. It takes O(2*N) space .
https://codeforces.com/blog/entry/18051