Fenwick Tree

aka Binary Indexed Tree(BIT)

Fenwick tree gives you same time complexity for Point Update and Range Query as a segment tree. It requires $O(N)$ memory but the constant factor is smaller than segment trees, generally around $2N$.

Fenwick tree though can only support a function which has an $identity$ element and $inverse$ elements.

Generally everyone agrees that Segment Trees should be enough for most of the problems in Competitive Programming¹, I still find this data structure very interesting. People also say that it’s easier to code a Fenwick tree for multidimentional data.

There are some advance use cases of Fenwick trees as well, see the References.

References

• Sort-Fenwick: Fenwick Trees are More Powerful than I Thought - Codeforces
• Fenwick Tree - cp-algorithm
• Fenwick Tree, Sparse Table - YouTube

1. BIT vs Segmen Tree - Codeforces, Do I need to learn Fenwick Tree when I already know how to use Segment Tree? - Codeforces ↩