Fenwick Tree (Binary Indexed Tree) Explained — Internals, Edge Cases & Tricks

Competitive programmers love Fenwick Trees because they solve a brutally common problem — range prefix-sum queries with point updates — in O(log n) time AND O(n) space, with constants so small the code fits in about 10 lines. You'll find them inside database engines for order-book aggregations, in game servers tracking cumulative scores, and in every serious competitive programming solution that involves frequency arrays or inversions. If you've ever hit a TLE on a naive cumulative-sum approach, a Fenwick Tree is likely the fix.

The core problem is this: you have an array of numbers that changes over time, and you need to repeatedly answer 'what is the sum of elements from index 1 to index k?' A flat prefix-sum array answers queries in O(1) but updates in O(n). A Fenwick Tree gives you O(log n) for both, with a constant factor that is almost embarrassingly small — often 3–5x faster in wall-clock time than a segment tree for the same problem.

By the end of this article you'll understand exactly why the bit-manipulation trick i += i & (-i) works, how to extend the tree for range updates and point queries, how to do a binary search on the tree itself, and the exact production bugs that bite engineers the first time they ship this structure in real code.

What is Fenwick Tree — Binary Indexed Tree?

Fenwick Tree — Binary Indexed Tree is a core concept in DSA. Rather than starting with a dry definition, let's see it in action and understand why it exists.

// TheCodeForge — Fenwick Tree — Binary Indexed Tree example
// Always use meaningful names, not x or n
public class ForgeExample {
    public static void main(String[] args) {
        String topic = "Fenwick Tree — Binary Indexed Tree";
        System.out.println("Learning: " + topic + " 🔥");
    }
}

Frequently Asked Questions