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 Same Problem, Far Less Machinery

A Fenwick tree, also called a binary indexed tree or BIT, solves the same problem a segment tree solves: prefix sums with point updates, both in O(log n). Its appeal is that it does so with dramatically less code and memory.

A segment tree needs a 4n array, recursive build, query and update routines, and careful handling of identity elements. A Fenwick tree is one array of size n+1 and two loops of about three lines each. That compactness is why it is the default in competitive programming when the operation is a sum.

The core idea is a decomposition. Every integer is a sum of distinct powers of two — its binary representation — and the Fenwick tree uses the same decomposition on ranges. Rather than storing a tree of intervals explicitly, it stores at each index a partial sum over a range whose length is determined by that index's binary form.

Specifically, the entry at index i stores the sum of the lowbit(i) elements ending at position i, where lowbit(i) is the value of the lowest set bit of i. So index 8 (binary 1000) covers 8 elements, index 12 (1100) covers 4, and index 7 (0111) covers just 1.

This is why the structure must be 1-indexed. lowbit(0) is 0, so index 0 would cover a range of length zero and the traversal loops would never terminate. Allocating n+1 entries and leaving index 0 unused is not a stylistic choice — it is required for the arithmetic to work.

Same O(log n) guarantees as a segment tree, in one array
Index i stores the sum of the lowbit(i) elements ending at i
Range lengths come from the binary representation of the index
Must be 1-indexed — lowbit(0) is 0 and would loop forever

The Lowbit Trick

Everything depends on isolating the lowest set bit, and the standard expression is i & (-i). It is worth understanding rather than memorising, since it looks like it should not work.

In two's complement, -i is ~i + 1 — invert every bit, then add one. Inverting flips the lowest set bit to 0 and all the zeros below it to 1; adding one then carries through those ones and lands exactly on that bit position. The result is that i and -i agree on exactly one bit: the lowest set bit of i. Anding them isolates it.

For i = 12 (binary 1100), -i is 0100 in the low bits, and 12 & -12 gives 4. For i = 7 (0111), the result is 1. For i = 8 (1000), it is 8.

Two operations follow, and they move in opposite directions.

Removing the lowest set bit — i -= i & (-i) — jumps to the index covering the block immediately before the current one. This is the query direction, and it strictly decreases i toward zero.

Adding the lowest set bit — i += i & (-i) — jumps to the next index whose range contains position i. This is the update direction, and it strictly increases i toward n.

Each step clears or carries at least one bit, so each loop runs at most log₂ n times. That is the entire complexity argument: the number of iterations equals the number of set bits touched, bounded by the width of the integer.

One caution: i & (-i) relies on two's complement negation. In languages where the integer type is unsigned or arbitrary-precision, use i & (i ^ (i - 1)) or the language's equivalent — Python's arbitrary-precision integers happen to make i & -i work correctly anyway.

i & (-i) isolates the lowest set bit via two's complement
Subtract it to walk down for a prefix query
Add it to walk up for an update
Each loop runs once per set bit — at most log₂ n iterations

Query and Update

Prefix sum of the first i elements. Start with the total at 0 and index at i. While i is positive, add tree[i] to the total and then remove the lowest set bit. The loop accumulates disjoint blocks whose lengths are exactly the powers of two in i's binary representation, and together they tile [1, i] with no gaps and no overlaps.

For i = 13 (binary 1101), the walk visits index 13 covering 1 element, then index 12 covering 4, then index 8 covering 8 — 1 + 4 + 8 = 13 elements, exactly the prefix. That correspondence between the binary digits and the block lengths is the clearest way to see why the algorithm is correct.

Point update: add a delta to position i. Start at index i, add the delta to tree[i], then add the lowest set bit and repeat while the index is within bounds. This visits every index whose covered range includes position i, which is precisely the set of entries that need correcting.

Note the asymmetry that makes the structure work: the query walk descends and the update walk ascends, and the two visit disjoint index sets that together guarantee correctness. Confusing the directions produces a structure that returns plausible but wrong sums.

Range sum from l to r is prefix(r) − prefix(l − 1). Two prefix queries, each O(log n).

Building the tree can be done by calling update n times at O(n log n), but there is an O(n) method worth knowing: copy the array in, then for each index i, add tree[i] into tree[i + lowbit(i)] when that index is in range. One pass, no logarithm.

The point that determines whether a Fenwick tree applies at all: range queries are computed by subtraction. That requires the operation to be invertible, so sums and XOR work, but minimum and maximum do not — there is no way to subtract an element from a running minimum. A segment tree has no such restriction because it combines rather than subtracts, and this is the main reason to choose one.

Fenwick tree against segment tree
	Fenwick tree	Segment tree
Memory	n + 1 integers	4n nodes
Code size	Two short loops	Recursive build, query, update
Constant factor	Smaller	Larger
Prefix sum	O(log n)	O(log n)
Min / max queries	Not possible	O(log n)
Range updates	Needs two BITs	Lazy propagation
Choose when	The operation is a sum	Min, max, gcd, or complex merges

Query: add tree[i], then strip the lowest bit, until i is 0
Update: add the delta, then add the lowest bit, until past n
Range sum is prefix(r) − prefix(l−1) — two queries
Requires an invertible operation, so min and max are excluded

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.

Implementation

Update and query a Fenwick tree

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def update(self, i, delta):
        while i <= self.n:
            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('prefix(7) =', bit.query(7))

#include <iostream>
#include <vector>
using namespace std;
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;
    }
};
int main() {
    BIT bit(8);
    bit.update(3, 5);
    cout << "prefix(7) = " << bit.query(7) << '\n';
}

public class Main {
    static 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;
        }
    }
    public static void main(String[] args) {
        BIT bit = new BIT(8);
        bit.update(3, 5);
        System.out.println("prefix(7) = " + bit.query(7));
    }
}

Watch it run

Step through it

Running on size 8, add 5 at index 3, read prefix(7)

Output

Read all 13 Steps

One flat array Slots 1..8. Slot i covers a range whose length is exactly lowbit(i) = i & -i.
lowbit(4) 4 is binary 100, so lowbit is 4: slot 4 covers four elements, indices 1..4.
lowbit(6) 6 is binary 110. The lowest set bit is 2, so slot 6 covers only indices 5..6.
lowbit(7) 7 is binary 111 — lowest set bit 1, so slot 7 covers just itself.
Update index 3 Add 5 at index 3. Start at slot 3 and add the value there.
Climb: 3 → 4 Next slot is i + lowbit(i) = 3 + 1 = 4. Slot 4 covers index 3, so it must change too.
Climb: 4 → 8 4 + lowbit(4) = 4 + 4 = 8. Slot 8 covers the whole array, so it also changes.
Update done Past 8 we leave the array, so the update stops. Three slots touched — the number of set bits encountered, bounded by log n.
Query prefix(7) Sum indices 1..7. Start at slot 7 and walk downward this time.
Strip: 7 → 6 i - lowbit(i) = 7 - 1 = 6. Add slot 6, which covers indices 5..6.
Strip: 6 → 4 6 - 2 = 4. Add slot 4, covering indices 1..4 — including the 5 we inserted.
Strip: 4 → 0 4 - 4 = 0, so the walk ends. The ranges added were adjacent and non-overlapping by construction.
Range sums prefix(7) = 5. Any range [l, r] is prefix(r) - prefix(l-1), so the structure answers arbitrary ranges while only ever storing prefixes.

Extensions and Where It Fits

The plain structure gives point update and range query. Two variations extend it, and both are standard.

Range update with point query simply inverts the roles by storing a difference array in the BIT. Adding v to every element in [l, r] becomes two point updates — add v at l, subtract v at r+1 — and the value at any position is then the prefix sum up to it. Same two loops, different interpretation.

Range update with range query needs two Fenwick trees and a small piece of algebra, maintaining B1 and B2 such that the prefix sum is prefix(B1, i)·i − prefix(B2, i). It is more involved than lazy propagation to derive but far shorter to implement, which is why it remains popular.

The classic application beyond range sums is counting inversions — pairs where a larger element precedes a smaller one. Process the array left to right, and for each element query how many already-inserted values exceed it, then insert it. With coordinate compression to bound the value range, this is O(n log n), and it is the standard alternative to counting inversions during a merge sort.

The same shape solves 'count of smaller elements to the right' and, extended to two dimensions with a BIT of BITs, answers rectangle sum queries on a grid in O(log² n) with far less memory than a 2-D segment tree.

Choosing between the two structures comes down to one question first: is the operation invertible? If it is a sum or an XOR, take the Fenwick tree — it is a fraction of the code, uses a quarter of the memory, and has a smaller constant factor. If it is a minimum, maximum, gcd, or anything requiring lazy range updates, the segment tree is the only option that works.

Both are O(log n), so the choice is about applicability and constant factors rather than asymptotics.

Store a difference array for range updates with point queries
Two BITs give range update with range query
Counting inversions in O(n log n) is the classic use
Invertible operation → Fenwick; min, max or lazy → segment tree