Fenwick Tree (Binary Indexed Tree)

A compact array structure that maintains prefix aggregates with logarithmic update and query using the low-bit trick.

Prefix sums that update

A Fenwick tree, or binary indexed tree (BIT), keeps prefix sums of a mutable array in O(log n) per point update and prefix query, using only a single array of length n and no explicit tree nodes. It exploits the binary representation of indices: node i is responsible for a block of length equal to its lowest set bit.

The low-bit trick

Kronos motion — classical

The expression i & (-i) isolates the least significant set bit of i. To query a prefix, repeatedly subtract that bit to walk toward zero; to update, repeatedly add it to walk toward n. Each walk touches O(log n) indices because it clears or advances one bit at a time.

Core operations

python

tree = [0]*(n+1)  # 1-indexed

def update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & (-i)

def prefix(i):        # sum of a[1..i]
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & (-i)
    return s

def range_sum(l, r):
    return prefix(r) - prefix(l-1)

Beyond sums

Range-update point-query: store differences, update two endpoints.
Range-update range-query: keep two Fenwick trees to correct the offset.
2D Fenwick trees give O(log^2 n) rectangle sums on a grid.
Order statistics: over a value-indexed BIT, binary-lift to find the k-th smallest in O(log n).

Trade-offs

Fenwick trees are shorter and have smaller constants than segment trees, but they require the aggregate to be invertible (subtraction). For min, max, or gcd without inversion, use a segment tree or sparse table instead.