Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query

WHY does this structure exist?

WHAT is stored in each cell? (the lowbit insight)

For an array of values $a_1, a_2, \dots, a_n$ (1-indexed), define the Fenwick cell

$\text{tree}[i] = \sum_{k=i-\text{lowbit}(i)+1}^{i} a_k$

where ==$\text{lowbit}(i) = i \,\&\, (-i)$== is the value of the lowest set bit of $i$.

So cell $i$ stores the sum of the $\text{lowbit}(i)$ elements ending at index $i$.

HOW: deriving query from scratch

We want $\text{prefix}(i) = a_1 + a_2 + \dots + a_i$.

Step 1. Cell $i$ already gives us the last block: $\sum_{k=i-\text{lowbit}(i)+1}^{i} a_k$. Why? That's literally its definition.

Step 2. What's left is $\text{prefix}(i - \text{lowbit}(i))$ — the part before that block. Why? Removing the lowbit-sized chunk leaves us needing the prefix up to a smaller index.

Step 3. Recurse: keep adding $\text{tree}[i]$ and stripping the lowest bit until $i=0$. Why this terminates fast? Each step removes one set bit from $i$, so it runs at most (number of set bits) $\le \log_2 n$ times.

$\boxed{\text{prefix}(i) = \sum \text{tree}[i],\quad i \leftarrow i - \text{lowbit}(i)\ \text{until } i=0}$

def query(tree, i):          # prefix sum a[1..i]
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & (-i)        # strip lowest set bit
    return s

HOW: deriving update from scratch

Adding $\delta$ to $a_j$ must fix every cell whose block contains index $j$.

Step 1. Cell $j$ contains $a_j$ (its block ends at $j$). Add $\delta$ there. Step 2. The next cell up that contains $j$ is at index $j + \text{lowbit}(j)$. Why? The next larger block that still includes $j$ starts at the same left edge but extends further; its index is $j$ plus its own lowbit, which equals $j+\text{lowbit}(j)$ by the nesting structure of these blocks. Step 3. Repeat while $j \le n$.

$\boxed{\text{update: } \text{tree}[j] \mathrel{+}= \delta,\quad j \leftarrow j + \text{lowbit}(j)\ \text{until } j>n}$

def update(tree, n, j, delta):   # a[j] += delta
    while j <= n:
        tree[j] += delta
        j += j & (-j)            # go to next responsible cell

A range sum $[l, r]$ is just $\text{query}(r) - \text{query}(l-1)$.

Worked examples

Common mistakes

Complexity

Linear build (the 80/20 trick): initialize tree[i] = a[i], then for each $i$ from 1 to $n$, push your block sum into your parent: if i+lowbit(i) <= n: tree[i+lowbit(i)] += tree[i]. Why? Each cell first becomes complete, then donates its block to the next responsible cell — one pass, $O(n)$.

Connections

• Prefix sum array — the $O(1)$-query, $O(n)$-update baseline Fenwick improves on.
• Segment tree — more general (any associative op, range updates), but heavier; Fenwick is the lean special case for sums.
• Two's complement representation — why i & -i isolates the lowest set bit.
• Binary representation of integers — set bits = number of query/update steps.
• Inversion counting / Order statistics — classic Fenwick applications.
• Range update with difference array — combine with BIT for range-update/point-query.

Concept Map

Hinglish (regional understanding)