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

Step 1 — The problem, drawn as a row of boxes

WHAT. We have a row of numbered boxes. Box number $i$ holds a value $a_{i}$ . We number them starting at $1$ (not $0$ — that choice matters later, and we will see exactly why).

WHY. Before inventing a clever structure, look at the enemy. A prefix sum up to box $i$ means "add everything from box $1$ to box $i$ ." Written out:

$prefix (i) = box 1 a_{1} + box 2 a_{2} + \dots + box i a_{i}$

Every symbol here: $a_{1}, \dots, a_{i}$ are the numbers inside the boxes; the $+$ signs are ordinary addition; $prefix (i)$ is the single total we want. Doing this the naive way visits every box — that is $i$ steps, which for a big row is slow.

PICTURE. Below, the top row is the raw data. The bracket shows the six boxes a naive $prefix (6)$ would have to touch one by one.

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

Step 2 — The lowbit ruler: how binary tells us a block size

WHAT. Write each box number in binary (base-2: each digit is a power of two, $\dots 8, 4, 2, 1$ ). The lowest set bit of a number is the rightmost $1$ in that binary writing, read as its own power of two. We call it $lowbit (i)$ .

WHY this tool and not another. We need a rule that assigns each box a block length so that (a) big blocks and small blocks nest neatly, and (b) the rule is computable in one machine instruction. The rightmost binary $1$ does both: it is the largest power of two that divides $i$ , and hardware computes it with $i & (- i)$ . We reach for binary precisely because "powers of two" and "nesting" are the same idea in binary.

$lowbit (i) = i & (- i)$

Term by term: $i$ is the box number; $- i$ is its negative written in two's complement (flip all bits, add $1$ ); $&$ is bitwise-AND (keep a bit only where both have a $1$ ). The flip-and-add-one leaves every bit above the rightmost $1$ disagreeing, so only that single rightmost $1$ survives the AND.

PICTURE. The board shows $12 = 110 0_{2}$ next to $- 12$ ; the AND lights up exactly the $10 0_{2} = 4$ bit.

See Binary representation of integers if the base-2 writing itself feels new.

Step 3 — Each cell owns a block ending at itself

WHAT. We keep a second array, $tree$ , the same length as the data. Cell $tree [i]$ does not store $a_{i}$ alone — it stores the sum of a block of consecutive values that ends at $i$ and has length $lowbit (i)$ :

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

Term by term: the sum runs over $k$ ; it ends at $k = i$ (right edge of the block); it starts at $k = i - lowbit (i) + 1$ (walk left by $lowbit (i)$ boxes, then $+ 1$ to land on the first box inside the block). So the block has exactly $lowbit (i)$ boxes.

WHY. If short indices own short blocks and indices divisible by big powers of two own big blocks, then a few of these blocks tile any prefix — that is the payoff we cash in Step 4.

PICTURE. Each cell drawn as a horizontal bar showing which raw boxes it covers. Notice how bars of length $1, 2, 4, 8$ stack like a staircase.

$i$	binary	lowbit	covers $a_{k}, k \in$
4	$100$	4	$[1, 4]$
6	$110$	2	$[5, 6]$
7	$111$	1	$[7, 7]$
8	$1000$	8	$[1, 8]$

Step 4 — Query: cover a prefix with a few bars (walk DOWN)

WHAT. To get $prefix (i)$ , add $tree [i]$ , then jump to the box just left of that block by subtracting the lowbit, and repeat until you fall off the left edge (reach $0$ ):

$prefix (i) = \sum tree [i], i \leftarrow i - lowbit (i) until i = 0$

Term by term: $tree [i]$ contributes one bar; $i - lowbit (i)$ is the box where the next bar's right edge sits (we chopped off exactly the block we just used); the loop stops at $i = 0$ because there is nothing before box $1$ .

WHY it is fast. Each subtraction erases the rightmost $1$ from $i$ 's binary form. A number with at most $lo g_{2} n$ bits has at most $lo g_{2} n$ ones, so at most $lo g n$ bars are added. This is the whole speedup, and it comes for free from the lowbit rule of Step 2.

PICTURE. For $prefix (6)$ : start at $6$ (bar $[5, 6]$ ), drop to $6 - 2 = 4$ (bar $[1, 4]$ ), drop to $4 - 4 = 0$ stop. Two bars tile $[1, 6]$ perfectly — no overlap, no gap.

Compare this to a plain Prefix sum array: that array answers the query in one step but pays $O (n)$ per update — the trade we are escaping.

Step 5 — Update: fix every bar covering a box (walk UP)

WHAT. To add $δ$ to $a_{j}$ , we must repair every bar whose block contains box $j$ . Start at $tree [j]$ , then climb by adding the lowbit, until we pass the end $n$ :

$tree [j] + = δ, j \leftarrow j + lowbit (j) until j > n$

Term by term: $tree [j]$ is the smallest bar containing box $j$ (its block ends at $j$ ); $j + lowbit (j)$ is the index of the next larger bar that still swallows box $j$ — its left edge is the same or further left, and by the nesting of Step 3 its index is exactly $j$ plus its own lowbit; the loop stops once $j$ exceeds the array size $n$ .

WHY the opposite direction. Query chops the rightmost $1$ (goes toward $0$ ); update carries into the next bit (goes toward $n$ ). They walk the same lowbit ladder in mirror directions — that symmetry is the heart of the structure.

PICTURE. Updating box $3$ : the arrow climbs $3 \to 3 + 1 = 4 \to 4 + 4 = 8 \to 16 > 8$ stop. Highlighted bars $tree [3], tree [4], tree [8]$ are exactly the ones covering box $3$ .

Step 6 — Range sums by subtracting two prefixes

WHAT. A sum over $[l, r]$ is two prefix queries subtracted:

$range (l, r) = prefix (r) - prefix (l - 1)$

Term by term: $prefix (r)$ is everything up to $r$ ; $prefix (l - 1)$ is everything strictly before $l$ ; subtracting cancels boxes $1 \dots l - 1$ and leaves exactly $a_{l} + \dots + a_{r}$ .

WHY $l - 1$ , not $l$ . Box $l$ itself belongs to the range, so we must remove only what comes before it. Using $prefix (l)$ would wrongly delete $a_{l}$ .

PICTURE. Two brackets — the big one $[1, r]$ minus the small one $[1, l - 1]$ — leaving the middle strip $[l, r]$ shaded.

Step 7 — The degenerate case: why box 0 breaks everything

WHAT. Look at $lowbit (0)$ . Zero in binary is all $0$ s — it has no rightmost $1$ . So $0 & (- 0) = 0$ .

WHY it is fatal. In the update loop, $j \leftarrow j + lowbit (j) = 0 + 0 = 0$ — the index never moves, an infinite loop. In the query loop, we stop the moment $i = 0$ , so an index of $0$ contributes nothing and can never start a walk. Index $0$ has no block. That is the real reason a Fenwick tree lives on indices $1 \dots n$ ; if your data is $0$ -indexed, shift it by one.

PICTURE. The board shows the number line: every positive index has a rightmost $1$ (an arrow of length lowbit), but $0$ is a dead stop with a zero-length arrow.

The one-picture summary

Everything above compressed: the raw boxes on top; the staircase of bars (lengths $1, 2, 4, 8$ ) below; a blue query path chopping down from $6$ to $0$ ; a pink update path climbing up from $3$ past $8$ . Query and update are the same ladder walked in opposite directions.

Recall Feynman: the whole walkthrough in plain words

Picture a shelf of numbered candy jars. Instead of counting jars one by one to know "how much candy in the first six jars," some jars keep a pre-bundled subtotal of a chunk of jars ending at them. How big is the chunk? Look at the jar's number in binary and find the rightmost 1 — that power of two is the chunk length (jar $6 = 110$ , rightmost $1$ is $2$ , so it bundles $2$ jars: $5$ and $6$ ). To total the first six, you grab jar $6$ 's bundle (jars $5, 6$ ), then step back to jar $4$ whose bundle is jars $1$ – $4$ — two grabs, done, no gaps. To change one jar, you fix only the bundles that contain it, found by repeatedly adding the rightmost-1 chunk (jar $3 \to 4 \to 8$ ). Grabbing bundles walks down toward zero; fixing bundles walks up toward the end — same ladder, opposite ways. And jar $0$ ? It has no rightmost $1$ , no chunk, so it never plays — which is exactly why we number from $1$ .

Recall Self-test

For $prefix (7)$ , which cells add up? ::: $tree [7]$ (bar $[7, 7]$ ) then $7 - 1 = 6$ : $tree [6]$ (bar $[5, 6]$ ) then $6 - 2 = 4$ : $tree [4]$ (bar $[1, 4]$ ) then stop. Cells $7, 6, 4$ . Which cells does updating box $5$ touch (n=8)? ::: $5 \to 5 + 1 = 6 \to 6 + 2 = 8 \to 16 > 8$ . Cells $5, 6, 8$ . Why does query terminate in $\leq lo g_{2} n$ steps? ::: Each subtraction deletes one binary $1$ from the index; a number below $n$ has $\leq lo g_{2} n$ ones.

Connections

Parent: Fenwick tree (Binary Indexed Tree) — prefix sums, O(log n) update and query
Contrast the trade-offs: Prefix sum array, Segment tree
Bit machinery behind lowbit: Two's complement representation, Binary representation of integers
Applications built on this: Inversion counting, Order statistics, Range update with difference array