Fenwick Tree (Binary Indexed Tree)

Introduction: The “Prefix Sum” Problem

If you need to calculate the sum of the first $K$ elements (Prefix Sum) of an array that is constantly changing:

• Static Prefix Sum Array: $O(1)$ for query, but $O(N)$ to update. Too slow for frequent changes.
• Segment Tree: $O(\log N)$ for both, but complex to implement and uses $4N$ memory.

Fenwick Tree (also known as BIT) is the perfect middle ground. It provides $O(\log N)$ for both query and update using only $1N$ memory and about 10 lines of code.

What Problem does it solve?

• Input: An array with frequent “Add X to element at index i” operations.
• Output: Quick calculation of the sum of elements in a range [L, R].
• The Promise: High-performance, low-memory prefix sums.

Core Idea (Intuition)

The Fenwick Tree is based on Binary Representation. Every integer can be broken into a sum of powers of two (e.g., $7 = 4 + 2 + 1$). In a Fenwick Tree, each node at index i stores the sum of a range whose length is determined by the last set bit of i (lowbit).

• Index 4 (100 in binary) stores the sum of 4 elements.
• Index 6 (110 in binary) stores the sum of 2 elements.
• Index 7 (111 in binary) stores the sum of 1 element.

To get the sum of the first 7 elements, you just add tree[7] + tree[6] + tree[4].

How it Works

1. Lowbit: i & -i extracts the lowest power of 2 that divides i.
2. Update: To add a value at index i, you move up the tree by adding lowbit to i until you hit $N$.
3. Query: To get the sum up to i, you move down the tree by subtracting lowbit from i until you hit 0.

Typical Business Scenarios

• ✅ Real-time Dashboards: A counter of “Total Sales Today” that increments with every transaction.

• ✅ Competitive Programming: Any problem requiring dynamic prefix sums.

• ✅ Signal Processing: Computing cumulative distribution functions (CDF) of live signals.

• ❌ Non-Invertible Operations: Fenwick Trees are great for Sums (because you can do Sum(R) - Sum(L-1)). They are harder to use for Range Minimum Query (RMQ) because “Minimum” is not easily reversible. Use a Segment Tree or Sparse Table for RMQ.

Performance & Complexity

• Query (Sum): $O(\log N)$.
• Update (Add): $O(\log N)$.
• Space: $O(N)$.

Summary

“Fenwick Tree is the ‘Minimalist’s Segment Tree’. It uses binary arithmetic to provide logarithmic performance with zero memory overhead. If you only need range sums, don’t build a massive tree—use a BIT.”