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.

Achromatic

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.

Halfslip

So, asymptotically (i.e. ignoring constant factors), a Segment Tree is strictly better than a Fenwick Tree? Can a Fenwick Tree do anything faster than Segment Tree asymptotically? – Achromatic

You keep talking about BITs, while the OP asked about Fenwick Trees. Are BITs Fenwick Trees? That needs to be stated if so. – Polybasite

Usually everyone knows it, but for people who don't know, your comment would help. Happy Learning! – Halfslip

@Polybasite yes, BITs and fenwick trees are the same thing – Martel

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.

Basic

Fenwick tree can be build in O(N). Instead of calling update on each entry, iterate through each element and update the array's value to the immediate parent. And we can use Fenwick's tree for L != 1 also by computing R and inverse function with computed L. i.e. if summation is the function then you find for R and L and subtract the results of L from R to get the answer. – Indisposed

What is this L you're mentioning ni L = 1 ? – Monseigneur

@Brainless, L is the leftmost element of the query range, R the rightmost; he implied that Fenwick trees are good only when you query to know the value for [1, x] ranges, which is wrong, since you can still derive every query [n, y] (assuming n < y) from computing the result for [1, x] and then subtracting the value of [1, n - 1] from it. – Heflin

Answer 3

Comment on Harsh Hitesh Shah answer: The last point against using a Fenwick tree, does not hold in general. Proof by counter example: Lets say we have a Fenwick tree for prefix sums, the function query(x) returns the prefix sum starting from first index 1 upto and including index x. If we would like to compute the sum for some interval [L, R], with 1 < L <= R <= N, we can just take query(R)-query(L-1).

Enthrall

Answer 4

Some additional information:

• Segment trees can be stored also be stored implicitly (just like a heap), and this will take up 2n space
• Fenwick trees are an online data structure, meaning that you can add elements to the end, just like an array, and it will still work. Segment trees do not have this property by default. If you are storing them implicitly, you can achieve both append and prepend operations in amortized O(log(n)) by doubling the size of the segment tree (just like amortized O(1) arrays). You need to study what the segment tree looks like in memory and then put the new space accordingly (you can't just put all the extra space at one end). Keep in mind that since the segment tree already takes 2n space, every time you double the array you now have 4n space usage
• Fenwick trees are faster and extremely simple to implement. The asymptotic bounds are equivalent, but the most basic query and update code is almost branchless, non-recursive, and uses very few operations. The segment tree versions of this can be made almost as fast, but this does take extra effort. Thankfully this only matters in very large inputs, as storing a segment tree implicitly has excellent spatial locality which gives it a good boost compared to storing pointers
• Fenwick trees cannot compute the inverse query in log(n) (to my knowledge); that is if we are storing partial sums for example, and I want to know what index i evaluates to a partial sum s, that will take log(n)^2. This process is trivial in log(n) for a segment tree
• There are a variety of other queries that segment trees can do, many of which are not possible on a Fenwick tree. You are paying for this extra flexibility with the 2n storage cost, of course

Edit: you can compute this query in log(n)! Here is my implementation:

def find(self, s):
    b = 1
    while b < len(bit):
        b <<= 1
    b >>= 1
    index = 0
    cur = 0
    while b > 0:
        if bit[index + b] + cur <= s:
            index += b
            cur += bit[index]
        b >>= 1
    return (index, cur)

This will return the index and sum that were closest to the target partial sum (will always be <= target). I don't believe this works with negative numbers in the BIT, however.

Good segment tree writeup: https://cp-algorithms.com/data_structures/segment_tree.html

Phloem