Lesson 5 · Advanced structures and algorithms

Fenwick Trees

Fenwick Trees, or Binary Indexed Trees (BIT), provide O(log N) range queries and point updates using clever bitwise operations instead of explicit tree nodes.

The Memory Advantage

Segment trees are powerful but consume 4N memory and carry the overhead of recursive traversal. A Fenwick Tree achieves the exact same time complexity for prefix sums but uses an array of exactly size N, relying entirely on the binary representation of indices to route updates.

The Least Significant Bit

The core mechanic of a Fenwick Tree is isolating the lowest set bit in an index, typically done with the bitwise operation i & -i. This bit determines the size of the range that the current array index is responsible for aggregating.

Key reference

Terms, operations, and practical uses

Binary Indexing

LSB IsolationThe bitwise operation i & -i isolates the lowest set bit of an integer, dictating the interval size.
Interval ResponsibilityAn index i in the Fenwick array stores the aggregate for the interval (i - LSB(i), i].
1-Based IndexingFenwick trees strictly require 1-based indexing for the bitwise mathematics to function correctly.

Core Operations

Prefix Sum QueryCalculated by starting at i and repeatedly stripping the LSB (i -= i & -i) while accumulating values.
Point UpdateAdding a value at i cascades forward by repeatedly adding the LSB (i += i & -i) to update all encompassing intervals.
ConstructionCan be built by performing N point updates in O(N log N), or optimally in O(N) by passing aggregates to the direct parent.

Comparisons

Memory ProfileRequires exactly O(N) auxiliary space, heavily outperforming the 4N requirement of Segment Trees.
ImplementationConsists of fewer than 10 lines of code, lacking the overhead of recursive function calls.
LimitationsCannot easily handle non-invertible operations (like finding the Maximum) without maintaining a secondary array.

Code example

Update a Fenwick tree

class BIT:
    def __init__(self, size):
        self.tree = [0] * (size + 1)
    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
bit = BIT(8)
bit.update(3, 5)
print('BIT Updated')

class BIT {
    vector<int> tree;
public:
    BIT(int n) : tree(n + 1, 0) {}
    void update(int i, int delta) {
        for (; i < tree.size(); i += i & -i)
            tree[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i)
            sum += tree[i];
        return sum;
    }
};

class BIT {
    int[] tree;
    BIT(int n) { tree = new int[n + 1]; }
    void update(int i, int delta) {
        for (; i < tree.length; i += i & -i)
            tree[i] += delta;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i)
            sum += tree[i];
        return sum;
    }
}

Inputadd a value at one array index

OutputBIT Updated

Example

Run the example step by step

Output

Cascading Updates

When a value is added to index i, it doesn't just update itself. It cascades forward to update all larger intervals that encompass index i. We simply add the lowest set bit to the index repeatedly (i += i & -i) until we hit the end of the array.

Summing the Prefix

To calculate the prefix sum up to index i, we do the reverse. We take the value at i, and repeatedly strip away the lowest set bit (i -= i & -i), accumulating the precomputed sums of adjacent, non-overlapping intervals until we reach zero.