The Fenwick Tree (invented by Peter Fenwick in 1994) is one of the most compact data structures ever devised. It gives you the full power of a dynamic segment tree in just one flat array of size N with 10 lines of code.

1. The Secret: Powers of 2 Range Decomposition

Any positive integer can be uniquely represented as a sum of powers of 2. For example: 13 = 8 + 4 + 1.

Fenwick took this idea and applied it to prefix ranges: instead of storing every single element, tree[i] stores the sum of a contiguous range of length equal to its lowest set bit!

The length of the range responsible by index i is given by: lowbit(i) = i & (-i).

• If i = 12 (1100_2): lowbit(12) = 4. So tree[12] stores the sum of 4 elements: indices [9, 10, 11, 12]!
• If i = 8 (1000_2): lowbit(8) = 8. So tree[8] stores the sum of the first 8 elements: [1 ... 8]!

2. The Two Operations

A. Prefix Sum Query: `i -= (i & -i)`

To calculate the prefix sum up to index 13:

1. Read tree[13] (covers index 13). 13 - lowbit(13) = 13 - 1 = 12.
2. Read tree[12] (covers indices 9 through 12). 12 - lowbit(12) = 12 - 4 = 8.
3. Read tree[8] (covers indices 1 through 8). 8 - lowbit(8) = 8 - 8 = 0 (Done!).

Total reads: only 3 steps to sum 13 numbers! At each step, you strip off one binary bit, taking at most O(log N) operations.

B. Point Update: `i += (i & -i)`

When you add delta to element i, which parent ranges need to be updated? Every index whose range covers i! You navigate up the tree simply by adding the lowest set bit: i += (i & -i)!

Clean C++20 Implementation

#include <vector>
#include <cstdint>

class FenwickTree {
    std::vector<int64_t> tree;
    int n;

    static inline int lowbit(int x) {
        return x & (-x);
    }

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

    // Adds delta to index i (1-indexed) in O(log N)
    void update(int i, int64_t delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    // Computes sum of prefix [1 ... i] in O(log N)
    int64_t query(int i) const {
        int64_t sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    // Computes range sum [l ... r] in O(log N)
    int64_t queryRange(int l, int r) const {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

Why Fenwick Beats Segment Trees in Production