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

This page assumes nothing. Before we can even read the parent note's first formula, we must earn every symbol in it: what a prefix sum is, how integers look in binary, what "the lowest set bit" means, what & and -i do, and why $O (lo g n)$ shows up. We build them in the order they depend on each other.

0. Counting numbers in a row (the array $a$ )

Picture it: boxes in a line, each with a label on top (1, 2, 3, …) and a value inside.

We choose to start counting at 1, not 0. Most programming languages start at 0, but — as you'll see in Section 4 — the whole Fenwick trick collapses at index 0, so we deliberately leave slot 0 empty and use $1 \dots n$ .

Related idea in the vault: Prefix sum array.

1. Prefix sum — the question we keep asking

The little " $\sum$ " symbol you'll meet later just means "add all of these up". So $\sum_{k = 1}^{i} a_{k} is read "add a_{k} for every k from 1 to i " .$ The letter $k$ is a counter that walks through the addresses one by one — it isn't a fixed number, it's a placeholder.

Why the topic needs this: almost every question about a range of numbers ("what's the sum from box 3 to box 6?") reduces to a difference of two prefix sums: $sum of [l, r] = prefix (r) - prefix (l - 1) .$ So if we can compute prefix sums fast, we can answer range questions fast. That is the entire goal.

2. Integers in binary — the alphabet of the trick

For example $12$ in binary is $110 0_{2}$ (the small $_{2}$ means "this is base two"): $110 0_{2} = 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 0 \cdot 1 = 12.$

Picture it: think of switches. Each switch is worth double the one to its right. A number is which switches are ON.

A switch that is ON is called a set bit (bit = binary digit). The switch furthest to the right that is ON is the lowest set bit — "lowest" because it's the smallest power of two that's turned on.

Vault prerequisite: Binary representation of integers.

Notice the pattern: the lowest set bit is the largest power of two that divides the number evenly. $12 = 4 \times 3$ , so $4$ is that power. This is exactly the "block length" the parent note uses.

3. Negative numbers in a computer — two's complement

Before we can compute the lowest set bit with the slick formula $i & (- i)$ , we need to know what $- i$ even looks like in bits, and what $&$ does.

Picture it: lay two rows of switches on top of each other; the AND keeps only the switches lit in both rows.

Here is the magic that this produces. Take $i = 12 = \dots 0110 0_{2}$ .

step	bits
$i$	$\dots 01100$
flip all ( $\neg i$ )	$\dots 10011$
add 1 ( $= - i$ )	$\dots 10100$

Now line up $i$ and $- i$ and take the AND:

i = \dots 01100 - i = \dots 10100 i & (- i) = \dots 00100

Only one switch survives — the lowest set bit, here the $4$ 's place. That's $lowbit (12) = 4$ .

4. Why index 0 is forbidden

Now we can see the 1-indexing rule from Section 0 with fresh eyes.

$lowbit (0) = 0 & (- 0) = 0 & 0 = 0.$

Zero has no switches ON, so it has no lowest set bit. In the update loop j += lowbit(j) the step would be j += 0 — you never move, an infinite loop. In the query loop i -= lowbit(i) you subtract $0$ — you never make progress. That is why the Fenwick tree lives on indices $1 \dots n$ and slot $0$ is dead space.

5. Blocks that nest — the $Σ$ over a range

Put the pieces together. The parent defines each cell as $tree [i] = \sum_{k = i - lowbit (i) + 1}^{i} a_{k},$ which now reads plainly: "add up the $a_{k}$ starting from index $i - lowbit (i) + 1$ and ending at $i$ " — a block of exactly $lowbit (i)$ numbers ending at $i$ .

$i = 4$ , $lowbit = 4$ : block covers indices $1$ to $4$ (length 4).
$i = 6$ , $lowbit = 2$ : block covers indices $5$ to $6$ (length 2).
$i = 7$ , $lowbit = 1$ : block covers index $7$ only (length 1).

Picture it: short blocks for odd indices (lowest bit = 1), longer blocks for indices divisible by high powers of two. They stack so that any prefix is a few of them laid end to end, and any single element sits inside only a few of them — that "few" is $O (lo g n)$ .

6. What is $O (lo g n)$ and why it appears

Both Fenwick loops change one bit of the index per step (strip a set bit, or add a bit that carries). A number has at most $lo g_{2} n$ bits, so each loop runs at most $lo g_{2} n$ times. That is the source of the $O (lo g n)$ speed. This is the same "logarithmic tree height" idea that powers the Segment tree.

Prerequisite map

Equipment checklist

Test yourself — reveal only after you've answered.

What does

a_{i}

mean and why do we start counting at 1?

a_{i}

is the value at position

i

; we start at 1 because

lowbit (0) = 0

would freeze the Fenwick loops.

What is

prefix (i)

in words?

The sum of all elements from position 1 up to and including

i

How is a range sum

[l, r]

built from prefix sums?

prefix (r) - prefix (l - 1)

What does

\sum_{k = 1}^{i} a_{k}

mean literally?

Add

a_{k}

for every counter value

k

from 1 to

i

Write 12 in binary and name its lowest set bit.

110 0_{2}

; lowest set bit value is 4.

What does

x & y

(bitwise AND) do?

Keeps a bit ON only where both

x

and

y

have it ON — the overlap of switch patterns.

How does a computer store

- i

Two's complement: flip all bits of

i

, then add 1.

Why does

i & (- i)

leave exactly the lowest set bit?

Below it there's no overlap (0s vs 1s), above it bits were flipped (disagree); only at the lowest set bit do both show 1.

What is

lowbit (0)

and why is that a problem?

0 — the loops would never advance (infinite loop / no start), so index 0 is banned.

What does

lo g_{2} n

count, and why does it bound the loops?

The number of binary digits of

n

; each loop step changes one bit, so at most

lo g_{2} n

steps run.

Connections

Parent: Fenwick tree topic
Builds on: Prefix sum array, Binary representation of integers, Two's complement representation
Leads to: Segment tree, Range update with difference array, Inversion counting, Order statistics