Binary Indexed Tree | Prefix Sums | O(log n) Update and Query
Picture a long shelf of jars, each holding some coins. A friend keeps asking, "How many coins are in the first 7 jars?" If you re-count from jar 1 every time, you do a lot of counting. Worse, every so often someone drops coins into one jar, so a single fixed total goes stale. You want two things to both be fast: add up the first few jars, and change one jar. A Fenwick tree (also called a Binary Indexed Tree, or BIT) gives you both.
The trick is to store clever partial sums instead of raw values. Each slot $bit[i]$ holds the sum of a small block of consecutive jars that ends at jar $i$. How long is that block? Exactly the value of the lowest set bit of $i$, written $\operatorname{LSB}(i) = i \mathbin{\&} (-i)$. For example $6 = 110$ in binary, its lowest set bit is $2$, so $bit[6] = A[5] + A[6]$. Likewise $bit[4]$ covers four jars $A[1\ldots4]$, and $bit[8]$ covers eight, $A[1\ldots8]$.
Both operations touch only $O(\log n)$ slots, because each step clears or adds one bit of an $n$-bit index. The two loops move in opposite directions: PREFIX-SUM walks down, $i \mathrel{-}= i \mathbin{\&} (-i)$, while UPDATE walks up, $i \mathrel{+}= i \mathbin{\&} (-i)$, touching exactly the blocks that contain position $i$. A range total is then $\text{RANGE-SUM}(l,r) = \text{PREFIX-SUM}(r) - \text{PREFIX-SUM}(l-1)$. That subtraction is the catch: BIT needs an invertible operation like $+$, which is why minimum and maximum (no inverse) need a segment tree instead. And the whole scheme is 1-indexed on purpose, since $\operatorname{LSB}(0) = 0$ would trap the loop forever.
Try this in the sim above: (1) drag the n slider higher and notice how few nodes a prefix query needs compared with $n$ itself. (2) Switch the preset between Sorted and Reverse and watch the operation and comparison counters in the stat cards. (3) Press Next repeatedly and follow the highlighted pseudocode line to see UPDATE climb with $i \mathrel{+}= i \mathbin{\&} (-i)$ and PREFIX-SUM descend with $i \mathrel{-}= i \mathbin{\&} (-i)$.
| Symbol | Meaning |
|---|---|
| n | Input size |
| T(n) | Time complexity function |
| h | Height or depth of structure |
| k | Key or rank parameter |
| W(n) | Worst-case complexity |
| A(n) | Average-case complexity |
X BIT is 0-indexed.
O BIT requires 1-indexed arrays because i & (-i) = 0 for i=0, causing infinite loop. Always use 1-indexed.
X BIT works for any aggregate function.
O BIT only works for invertible operations (addition, XOR). For min/max, use segment tree.
X PREFIX-SUM(i) is the same as the BIT array value bit[i].
O bit[i] stores only the range [i-LSB(i)+1..i]. PREFIX-SUM(i) combines multiple bit[] values to cover [1..i].
X Using i -= (i & -i) instead of i += (i & -i) in UPDATE.
O UPDATE goes UP (add LSB), PREFIX-SUM goes DOWN (subtract LSB). Swapping them gives wrong answers silently.
X Forgetting 1-indexed convention and using A[0].
O BIT is 1-indexed. If your array is 0-indexed, shift: bit[i+1] for A[i]. Using 0-indexed directly causes i&(-i)=0 infinite loop.
X Computing RANGE-SUM(l,r) as PREFIX-SUM(r) - PREFIX-SUM(l) instead of PREFIX-SUM(l-1).
O RANGE-SUM(l,r) = PREFIX-SUM(r) - PREFIX-SUM(l-1). Using PREFIX-SUM(l) excludes A[l] itself.