Fenwick Trees (Binary Indexed Trees): Fast Prefix Sums with Minimal Overhead

Proposed by Peter Fenwick in 1994, the Fenwick Tree—also known as a Binary Indexed Tree (BIT)—is an implicit tree structure represented entirely inside a simple flat array. It solves dynamic prefix sum queries and point updates in O(log N) time.

While a Segment Tree also accomplishes this in O(log N), a Fenwick Tree uses only O(N) auxiliary space (compared to 4 * N for Segment Trees), requires dramatically less code, and exhibits superior cache locality with lower runtime constant factors.

The Core Bitwise Trick: Lowest Set Bit (LSB)

The fundamental concept behind a Fenwick Tree is that every integer index can be uniquely decomposed into a sum of powers of 2. Each position `i` in the tree array stores the cumulative aggregate of an interval of length equal to its Lowest Set Bit (LSB).

Using two's complement representation, isolating the lowest set bit of an integer `i` is computed in a single assembly instruction:

int lsb = i & (-i);

• Example index 12 (binary 1100): `12 & (-12)` yields 4 (binary 0100). Thus, index 12 stores the aggregate of 4 elements: the range (8, 12].
• Example index 7 (binary 0111): `7 & (-7)` yields 1 (binary 0001). Thus, index 7 stores only its own single value.
• Example index 8 (binary 1000): `8 & (-8)` yields 8 (binary 1000). Thus, index 8 stores the cumulative sum from index 1 through 8.

Core Operations and Complexity

1. Prefix Query (sum from 1 to idx)

To compute the prefix sum up to index `idx`, accumulate `tree[idx]` and repeatedly strip off the lowest set bit (`idx -= idx & -idx`) until index reaches 0. Since an integer has at most log2(N) active bits, the traversal strictly visits O(log N) nodes.

2. Point Update (add delta to element at idx)

When modifying an element at `idx`, update `tree[idx]` and propagate the change upward to all ancestor intervals that cover this index by repeatedly adding the lowest set bit (`idx += idx & -idx`) until `idx` exceeds the array bounds N. Time Complexity: O(log N).

3. Range Query (sum from L to R)

Using the prefix difference identity, any contiguous range sum `[L, R]` evaluates instantaneously as: `query(R) - query(L - 1)`.

Fenwick Tree vs. Segment Tree Comparison

• Memory Footprint: Fenwick Tree uses exact N elements (1-indexed); Segment Tree requires up to 4 * N nodes.
• Code Complexity: A complete Fenwick Tree fits in roughly 15 lines of code; Segment Trees require recursive split/merge handlers.
• Invertible vs. Non-Invertible Operations: Fenwick Trees naturally support operations with algebraic inverses (like addition and XOR). For non-invertible operations (such as general Range Minimum Queries where updates can lower or raise values arbitrarily), Segment Trees are preferred.

C++ Implementation Blueprint

class FenwickTree {
private:
    int n;
    std::vector<long long> bit;

public:
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    // Point update: add 'val' to index 'idx' (1-based)
    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & (-idx)) {
            bit[idx] += val;
        }
    }

    // Prefix sum: query range [1, idx]
    long long query(int idx) {
        long long sum = 0;
        for (; idx > 0; idx -= idx & (-idx)) {
            sum += bit[idx];
        }
        return sum;
    }

    // Range sum: query range [l, r]
    long long queryRange(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

Real-World Applications & Classic Problems

1. Counting Inversions in an Array: Dynamically tracking previously seen coordinate ranks to compute total out-of-order pairs in O(N log N).
2. Dynamic Order Statistics: Combining a BIT with binary lifting to find the k-th smallest element in O(log N) without complex balanced binary search trees.
3. 2D Matrix Range Queries: Extending to a 2D Fenwick Tree with nested bitwise loops to support subgrid sum queries and point updates in O(log N * log M).
4. Continuous Cumulative Frequency Counters: Tracking real-time distribution frequencies in high-frequency trading and live sensor pipelines.