Fenwick Tree (BIT)

The trick

A Binary Indexed Tree (Fenwick tree) stores partial sums at indices chosen by the lowest set bit of i. Index i is responsible for a range of size i & (-i). This lets both update and prefix-sum run in O(log n) using only a single array.

Update & prefix sum

update walks up adding i & -i; prefix_sum walks down subtracting it. A range sum is prefix_sum(r) - prefix_sum(l-1).

bit = [0] * (n + 1)

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

def prefix_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

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

Output:

update(3, 5)
range_sum(1, 3)  # includes the +5 at index 3

Fenwick vs segment tree

Fenwick trees are shorter to code and use half the memory, but only naturally support prefix-reducible operations like sum/xor. Segment trees generalize to min/max/gcd and range updates — pick Fenwick for sums, segment tree for everything else.

Quick check

Pick the correct time complexity.

Quick check: A Fenwick tree's update and prefix-sum operations run in:

• O(1)
• O(log n)
• O(n)
• O(n log n)