Fenwick Trees and Binary Indexed Trees

You are streaming trade prints and need, at any moment, the running volume traded up to a given price level, while new prints keep arriving out of order. A plain running sum handles new prints in $O(1)$ but a prefix query means re-summing an array in $O(n)$. A Fenwick tree, also called a binary indexed tree (BIT), does both updates and prefix sums in $O(\log n)$, using nothing but an array.

The idea: each index owns a range determined by its lowest set bit

Instead of one array cell per raw value, a Fenwick tree stores partial sums, where cell $i$ covers a range of length equal to the lowest set bit of $i$ (in binary). Index 6 (110 in binary) has lowest set bit 2, so cell 6 covers indices 5–6. Index 8 (1000) has lowest set bit 8, so cell 8 covers indices 1–8. This layout is what makes both operations cheap:

• Update index $i$: add the delta to cell $i$, then move to $i + (i \mathbin{\&} -i)$ — jump to the next cell whose range includes $i$ — and repeat until past the array end.
• Query prefix sum up to $i$: read cell $i$, then move to $i - (i \mathbin{\&} -i)$ — strip off the lowest set bit — and repeat until $i$ reaches 0, summing as you go.

i & -i isolates the lowest set bit using two's-complement arithmetic; that one expression is the entire trick. Each operation touches at most $\log_2 n$ cells, because each step either sets a new bit or clears one, and an $n$-bit number has at most $\log_2 n$ bits.

Worked example

Start with all zeros over 8 slots. update(5, +3): add 3 to cell 5, jump to $5 + (5 \mathbin{\&} -5) = 5+1=6$, add 3 to cell 6, jump to $6+2=8$, add 3 to cell 8, jump to 16 (past the end), stop. Now query(6): read cell 6 (3), jump to $6-2=4$, cell 4 is 0, jump to $4-4=0$, stop. Prefix sum up to 6 is 3 — correct, since only index 5 has a nonzero value and $5 \le 6$.

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):        # O(log n)
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):                # prefix sum [1..i], O(log n)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

Where it shows up

Interview framing: "range sum query, mutable" (LeetCode 307), counting inversions in an array, and order-statistics variants (count of elements less than $x$ seen so far). On a desk, a Fenwick tree over price levels tracks cumulative order-book depth as orders arrive and cancel, and over time buckets it computes running P&L or volume-weighted stats without rescanning history on every tick.