The idea: prefix sums that can still change
You have an array A[1..n] and two jobs: change one element, and ask for a prefix sum sum(i) = A[1] + … + A[i]. A plain array makes the change O(1) but the sum O(n). A prefix-sum array makes the sum O(1) but a change O(n). A Fenwick tree, also called a binary indexed tree (BIT), does both in O(log n) with one extra array T[1..n] of the same size.
Box T[i] holds the sum of the lowbit(i) elements that end at i: T[i] = A[i − lowbit(i) + 1] + … + A[i]. On the canvas each box is a bar over the cells it covers, one row per box length, and every index is written in binary underneath. Indices are 1-based: index 0 has no lowest bit, so it is not used.
lowbit(i) = i & −i
lowbit is the value of the lowest 1 bit of i: lowbit(12) = lowbit(01100) = 00100 = 4. Computers store −i in two's complement: invert every bit and add 1. The +1 carries through the trailing 1s of the inverted number, so −i agrees with i on the lowest 1 bit and the zeros below it, and is the opposite everywhere above. i & −i keeps just that one bit (Demo: lowbit(12) = 12 & −12 = 4).
| binary (5 bits) | |
|---|---|
| 12 | 01100 |
| invert | 10011 |
| −12 = invert + 1 | 10100 |
| 12 & −12 | 00100 = 4 |
Prefix sum: walk down
To get sum(i), add T[i], which covers the last lowbit(i) cells, then jump to the cell just before that block: i −= lowbit(i). That clears the lowest 1 bit of i, so the walk stops after as many boxes as i has 1 bits, at most log₂ n + 1.
int sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i)
s += T[i];
return s;
}For 13 = 01101 the walk visits 13, 12 = 01100 and 8 = 01000: T[13] + T[12] + T[8] = A[13] + A[9..12] + A[1..8] = 1 + 18 + 41 = 60 (Demo: sum(13)). 15 = 01111 has four 1 bits, the most of any index up to 16, so it needs four boxes (Demo: sum(15), the worst case), while sum(16) is just T[16]. On the canvas the visited boxes turn blue, and so do the cells they cover: together they are exactly A[1..i], with no gaps and no overlap.
![Top: the boxes visited by sum(13), T[13], T[12] and T[8], in blue; they cover A[1..13]. Bottom: the boxes changed by add(5, +3), T[5], T[6], T[8] and T[16], in green; each of them covers A[5].](Images/fenwicktree/walks.svg)
Update: walk up
To add d to A[i], every box whose range contains i must change. The first is T[i]. The next box that also covers i is the parent i + lowbit(i): adding the lowest 1 bit makes the index's lowbit at least twice as big, so its box reaches back past i. Repeat until the index passes n.
void add(int i, int d) {
for (; i <= n; i += i & -i)
T[i] += d;
}Adding 3 to A[5] changes T[5], T[6], T[8] and T[16] (5 = 00101 → 00110 → 01000 → 10000), and nothing else (Demo: add 3 to A[5]). A later query then sees the change, because the boxes it adds are exactly the updated ones that lie inside its prefix (Demo: add 2 to A[3], then sum(7) sees it: 37 instead of 35).
Range sums and cost
A Fenwick tree answers prefix sums only, but any range is the difference of two prefixes: A[l..r] = sum(r) − sum(l − 1). For A[5..11] that is 52 − 17 = 35 (Demo: range sum A[5..11]; the boxes of the second walk are drawn red).
| Plain array | Prefix-sum array | Fenwick tree | Segment tree | |
|---|---|---|---|---|
| Change one element | O(1) | O(n) | O(log n) | O(log n) |
| Prefix or range sum | O(n) | O(1) | O(log n) | O(log n) |
| Extra memory | none | n | n | about 2n to 4n |
| Range min / max | O(n) | no | no (needs an inverse) | yes |
The Fenwick tree needs the operation to have an inverse (sum and difference, XOR) so that ranges can be subtracted. A segment tree also handles min and max and lazy range updates, at the cost of more memory and code. Like a binary heap, the tree is implicit: there are no pointers, only index arithmetic on one array.
Building the tree
Calling add once per element builds the tree in O(n log n). The page builds it in O(n): set T[i] = A[i], and for i = 1 to n add T[i] into its parent T[i + lowbit(i)]. Each box is complete before it passes its total up.
Fenwick trees count inversions, keep running frequency tables (how many values are ≤ x), and serve order-statistic queries in competitive programming; they were introduced for arithmetic coding, where the encoder needs cumulative symbol frequencies that keep changing.
For the same operations on a segment tree, side by side, see Segment Tree vs Fenwick Tree.
What the page leaves out
The page fixes n = 16 so every index fits in 5 bits. It leaves out the 0-based variant (i = (i & (i + 1)) − 1 and i |= i + 1), range updates with a second tree, finding the smallest i with sum(i) ≥ x by binary lifting over the powers of two, 2D Fenwick trees for matrix sums, and other invertible operations such as XOR.