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

This page is the stress test for the parent Fenwick tree note. We will not just re-solve one nice example — we will build a matrix of every kind of situation a Fenwick tree can be asked about, then work through examples until every cell of that matrix is covered.

Before we start, one reminder of the two moves, because every single example below is just these two moves on repeat:

Recall The only two operations (from the parent note)

Query (prefix sum $a_{1} + \dots + a_{i}$ ): start at $i$ , add $tree [i]$ , then set $i \leftarrow i - lowbit (i)$ , repeat until $i = 0$ . (walks DOWN toward 0)
Update (add $δ$ to $a_{j}$ ): start at $j$ , add $δ$ to $tree [j]$ , then set $j \leftarrow j + lowbit (j)$ , repeat while $j \leq n$ . (walks UP toward $n$ )
$lowbit (i) = i & (- i)$ = value of the lowest set bit. See Two's complement representation for why the negative-AND trick isolates that bit.

The scenario matrix

Here is every case class a Fenwick problem can throw at you. Each row is a distinct kind of trouble; the rightmost column names the worked example that nails it.

#	Case class	What could trip you	Example
A	Plain prefix query, positive values	pick the right jump path	Ex 1
B	Negative values in the array	sums can shrink, subtotals go negative	Ex 2
C	Point update, then re-query	which cells to fix	Ex 3
D	Range sum $[l, r]$	subtract $query (l - 1)$ not $query (l)$	Ex 4
E	Boundary indices ( $i = 1$ , $i = n$ )	shortest and longest jump paths	Ex 5
F	Zero / degenerate ( $query (0)$ , empty range)	loops that never run	Ex 6
G	Whole-array sum	single cell $tree [n]$ if $n$ is a power of two	Ex 7
H	Real-world word problem (running bank balance)	model it as point-update + prefix	Ex 8
I	Exam twist: recover a single element $a_{j}$	$a_{j} = query (j) - query (j - 1)$ , or a slicker way	Ex 9

Throughout, unless a new array is stated, we use this fixed test array (1-indexed, $n = 8$ ):

$a = [3, 2, - 1, 6, 5, 4, - 3, 3]$

The Fenwick cells for this array (built once) are:

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

Example 1 — Cell A: a plain positive-flavoured query

Worked example Compute

$query (7) = a_{1} + \dots + a_{7}$ . Forecast: Guess how many cells the path visits before you read on. (Hint: count the 1-bits of $7$ .)

Step 1. Write $7 = 11 1_{2}$ . $lowbit (7) = 1$ , so add $tree [7]$ and jump to $7 - 1 = 6$ . Why this step? Cell $7$ owns exactly the block $[7, 7]$ , i.e. $a_{7}$ . What remains to sum is the prefix up to $6$ .

Step 2. At $6 = 11 0_{2}$ , $lowbit (6) = 2$ : add $tree [6]$ , jump to $6 - 2 = 4$ . Why this step? Cell $6$ owns $[5, 6] = a_{5} + a_{6}$ . Now we still need the prefix up to $4$ .

Step 3. At $4 = 10 0_{2}$ , $lowbit (4) = 4$ : add $tree [4]$ , jump to $4 - 4 = 0$ . Stop (i=0). Why this step? Cell $4$ owns $[1, 4]$ , the whole remaining front chunk. Hitting $0$ means nothing is left.

So $query (7) = tree [7] + tree [6] + tree [4] = (- 3) + 9 + 10 = 16$ .

Verify: Direct sum $3 + 2 - 1 + 6 + 5 + 4 - 3 = 16$ . ✓ And $7 = 11 1_{2}$ has three 1-bits — path length was exactly 3. ✓

Example 2 — Cell B: negative values shrink the running total

Example 3 — Cell C: point update, then requery

Worked example Do

a[3] += 10, then recompute $query (3)$ and $query (6)$ . Forecast: Which cells change? Which prefixes change — does $query (2)$ change?

Step 1. $j = 3 = 01 1_{2}$ : add $10$ to $tree [3]$ ; jump to $3 + lowbit (3) = 3 + 1 = 4$ . Why this step? Index 3 lives inside cell 3's block $[3, 3]$ , so that subtotal must grow by $10$ .

Step 2. $j = 4 = 10 0_{2}$ : add $10$ to $tree [4]$ ; jump to $4 + 4 = 8$ . Why this step? Index 3 is inside block $[1, 4]$ owned by cell 4 — it also must grow.

Step 3. $j = 8 = 100 0_{2}$ : add $10$ to $tree [8]$ ; jump to $8 + 8 = 16 > n = 8$ . Stop. Why this step? Index 3 is inside $[1, 8]$ owned by cell 8. No larger cell exists, so we stop.

Now cells are $tree [3] = 9, tree [4] = 20, tree [8] = 29$ ; the rest unchanged.

Requery: $query (3) = tree [3] + tree [2] = 9 + 5 = 14.$ $query (6) = tree [6] + tree [4] = 9 + 20 = 29.$

Verify: New $a_{3} = 9$ . Direct $query (3) = 3 + 2 + 9 = 14$ . ✓ Direct $query (6) = 3 + 2 + 9 + 6 + 5 + 4 = 29$ . ✓ And $query (2)$ still uses only $tree [2]$ , which we never touched — it stays $5$ , correct because indices $1, 2$ are before the change. ✓

Example 4 — Cell D: range sum $[l, r]$ (the telescoping subtraction)

Example 5 — Cell E: boundary indices (shortest and longest paths)

Worked example Compute

$query (1)$ and $query (8)$ on the original array (before Ex 3's update). Forecast: One of these visits a single cell; the other visits a single cell too — but for opposite reasons. Guess which cell each hits.

Part A — $query (1)$ : Step A1. $1 = 000 1_{2}$ , $lowbit (1) = 1$ : add $tree [1] = 3$ , jump to $1 - 1 = 0$ . Stop. Why this step? Index 1 is the smallest possible; its block is exactly $[1, 1]$ . One cell, done. $query (1) = 3$ .

Part B — $query (8)$ : Step B1. $8 = 100 0_{2}$ , $lowbit (8) = 8$ : add $tree [8] = 19$ , jump to $8 - 8 = 0$ . Stop. Why this step? $8$ is a power of two, so it has a single 1-bit — cell 8 already owns the whole prefix $[1, 8]$ . One cell, done. $query (8) = 19$ .

Verify: $query (1) = a_{1} = 3$ . ✓ $query (8) = 3 + 2 - 1 + 6 + 5 + 4 - 3 + 3 = 19$ . ✓ Both boundary queries were length-1 paths — the extremes are the cheapest, not the most expensive.

Example 6 — Cell F: zero and degenerate inputs

Worked example What does

$query (0)$ return, and what is the range sum of the empty range $[4, 3]$ (where $l > r$ )? Forecast: Will these crash, or return a clean number?

Step 1. $query (0)$ : the loop condition is while i > 0. With $i = 0$ it never runs, so $s$ stays $0$ . Why this step? $lowbit (0) = 0 & 0 = 0$ — index $0$ has no lowest set bit, so there is nothing to strip and nothing to add. The parent note's warning ("Fenwick must be 1-indexed") is exactly this: index 0 is a dead end, which is why we deliberately use it as the "sum of nothing = 0" sentinel. $query (0) = 0$ .

Step 2. Empty range $[4, 3]$ : apply the range formula $query (3) - query (4 - 1) = query (3) - query (3) = 0$ . Why this step? An empty range contains no elements, so its sum must be $0$ . The formula gives that automatically — no special case needed.

Verify: Sum of zero elements is $0$ . ✓ The formula returning $0$ for $l = r + 1$ is the sanity check that our telescoping is consistent even at the degenerate edge.

Example 7 — Cell G: whole-array sum

Example 8 — Cell H: real-world word problem (running bank balance)

Worked example A bank account starts empty. Over 8 days the day-changes are

$a = [3, 2, - 1, 6, 5, 4, - 3, 3]$ (thousands of ₹, negatives are withdrawals). Someone corrects day 3's entry with a[3] += 10. What is the balance at end of day 6? Forecast: Balance at end of day 6 = prefix sum through day 6, after the correction. Guess the number.

Step 1. "Balance at end of day $t$ " = $a_{1} + \dots + a_{t} = query (t)$ . This is why a Fenwick tree fits: transactions are point updates (a day's amount changes), and balances are prefix queries. Why this step? Modeling: each transaction touches one day; each balance query is a running total — precisely the two Fenwick operations, both $O (lo g n)$ even if millions of days.

Step 2. Apply the correction: a[3] += 10 updates $tree [3], tree [4], tree [8]$ (exactly Ex 3).

Step 3. Balance = $query (6) = tree [6] + tree [4] = 9 + 20 = 29$ (in thousands ₹).

Verify: Day-by-day after correction: $3, 5, 14, 20, 25, 29$ — end of day 6 is $29$ . ✓ Units: thousands of ₹, a sum of daily ₹-changes, dimensionally consistent. So the balance is ₹29{,}000.

Example 9 — Cell I: exam twist — recover a single element $a_{j}$

Worked example Given only the Fenwick cells (original array), recover

$a_{7}$ and $a_{4}$ without rebuilding the array. Forecast: $a_{j} = query (j) - query (j - 1)$ always works. But for some $j$ there is a shortcut using just cells. Which $j$ ?

Step 1 (recover $a_{7}$ ). $a_{7} = query (7) - query (6)$ . Why this step? $query (7) - query (6)$ cancels $a_{1} + \dots + a_{6}$ , leaving exactly $a_{7}$ . From Ex 1, $query (7) = 16$ ; and $query (6) = tree [6] + tree [4] = 9 + 10 = 19$ . So $a_{7} = 16 - 19 = - 3$ .

Step 2 (recover $a_{4}$ , the slick way). For $a_{4}$ : $lowbit (4) = 4$ , so cell 4 owns block $[1, 4]$ . Then $a_{4} = tree [4] - (tree [3] + tree [2]) = 10 - (- 1 + 5) = 6.$ Why this step? $tree [4]$ sums $[1, 4]$ . To peel off $a_{4}$ alone, subtract the sub-cells covering $[1, 3]$ that sit "under" cell 4 — namely $tree [3]$ (block $[3, 3]$ ) and $tree [2]$ (block $[1, 2]$ ). This is faster than two full queries and is a classic exam trick; it mirrors how a Segment tree decomposes a node into children. (See also Order statistics and Inversion counting where recovering counts per index matters.)

Verify: Original array: $a_{7} = - 3$ ✓ and $a_{4} = 6$ ✓. Cross-check $a_{7}$ by the generic formula too — both routes agree.

Recall

Recall Quick self-test across the matrix

Cell B: is a negative subtotal a bug? ::: No — Fenwick only adds; negative block sums are fine. Cell D: range $[l, r]$ formula? ::: query(r) - query(l-1). Cell F: what is query(0)? ::: 0 — the loop never runs; index 0 has no lowbit. Cell G: when is the whole sum a single cell? ::: When n is a power of two, tree[n] owns [1,n]. Cell I: recover a single a_j generically? ::: a_j = query(j) - query(j-1). Cell E: which query indices give length-1 paths? ::: i=1 and any power of two (single set bit).

Connections

Parent: Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query (index 3.4.16)
Foundation for the range trick: Prefix sum array
Bit isolation behind $lowbit$ : Two's complement representation, Binary representation of integers
A heavier alternative that also does these queries: Segment tree
Applications that reuse point-update + prefix: Inversion counting, Order statistics, Range update with difference array