Eight cells, each summing a stretch of values set by the binary digits of its index. Watch a prefix sum hop left and an update hop right.
Ranges sized by binary digits
Eight cells, each the sum of a stretch set by its lowest bit
void add(int i, int x){ for (; i <= N; i += i & -i) bit[i] += x;} int prefix(int i){ int s = 0; for (; i > 0; i -= i & -i) { s += bit[i]; hops++; } return s;}int main(void){ const int a[N + 1] = { 0, 5, 2, 7, 1, 4, 8, 3, 6 }; for (int i = 1; i <= N; i++) add(i, a[i]); print_bit(); int s1 = prefix(7); printf("prefix(7) = %d in %d hops\n", s1, hops); add(4, 4); print_bit(); int s2 = prefix(7); printf("after add(4, 4): prefix(7) = %d\n", s2); return 0;}main has started.
- prefix(7)
- –
- hops
- 0
Output
Describe this picture
The picture is one row of eight boxes, the array bit from bit[1] to bit[8], with each index written above its box in binary, 0001 to 1000. Beneath the row are bars, one per box, in four lanes: each bar runs under the values that its box sums and ends under the box itself. Boxes 1, 3, 5 and 7 have a bar one value long in the nearest lane; boxes 2 and 6 have bars two long; box 4 has a bar four long, from 1 to 4; box 8 has a bar under all eight. A box written by the last line is outlined, and a marker above the row names the index i the program is at. Under the picture are the lines of fenwick.c the lesson discusses, with the line about to run marked, one sentence on the current step, two readouts (the prefix sum so far and the static count of hops) and the output. The clip plays once, about 14 seconds. First the eight values 5, 2, 7, 1, 4, 8, 3 and 6 go in, one add each; every add lights the boxes it changes, always the box of its own index and then boxes further right, until the row holds 5, 7, 7, 15, 4, 12, 3 and 36. Then prefix(7): it takes box 7, 3, then box 6, 12, then box 4, 15, each lit with its bar; the three lit bars together run from 1 to 7 without a gap, and the sum is 30 in 3 hops. Next add(4, 4) adds 4 to box 4, now 19, and box 8, now 40. The second prefix(7) gives 34, and the clip rests on the four lines of output. The transport plays and pauses, steps one line back or forward, and scrubs; a paused step is kept in the page address as fenwick.step.
Stretches set by the lowest bit
A Fenwick tree, or binary indexed tree, is one array the size of the data. Cell i does not hold a[i]. It holds the sum of a stretch ending at i, and the stretch is as long as the lowest 1 bit of i:
| i | binary | lowest 1 bit | stretch | bit[i] |
|---|---|---|---|---|
| 1 | 0001 | 1 | a[1] | 5 |
| 2 | 0010 | 2 | a[1] to a[2] | 7 |
| 3 | 0011 | 1 | a[3] | 7 |
| 4 | 0100 | 4 | a[1] to a[4] | 15 |
| 5 | 0101 | 1 | a[5] | 4 |
| 6 | 0110 | 2 | a[5] to a[6] | 12 |
| 7 | 0111 | 1 | a[7] | 3 |
| 8 | 1000 | 8 | a[1] to a[8] | 36 |
Cells are numbered from 1. Odd cells hold one value each; cells 2 and 6 hold two; cell 4 holds four; cell 8 holds all eight. Any prefix a[1] to a[i] is a few of these stretches laid end to end, one for each 1 bit of i.
The code and its cost
The lowest bit
i & -i is the lowest 1 bit of i. In two’s complement, -i is ~i + 1: every bit of i flipped, then 1 added, which carries up through the flipped low zeros and stops at the lowest 1 bit. Below that bit both i and -i have zeros, at it both have a 1, and above it they are opposites, so & keeps only that bit. For 6, which is 0110, -6 ends in 1010, and 6 & -6 is 0010, 2.
That is why cells are numbered from 1: 0 & -0 is 0, and a loop that steps by it would never move. a[0] in the program is a placeholder so that a[i] lines up with bit[i].
A prefix sum: clear the lowest bit
int prefix(int i)
{
int s = 0;
for (; i > 0; i -= i & -i) {
s += bit[i];
hops++;
}
return s;
}bit[i] covers the stretch that ends at i. Taking away its length, the lowest bit, gives the end of the stretch just before it. prefix(7) reads 7 (0111, a[7]), then 6 (0110, a[5] to a[6]), then 4 (0100, a[1] to a[4]), then reaches 0: 3 + 12 + 15 = 30. Each hop clears one 1 bit, so a prefix sum takes at most log₂ n + 1 hops.
An update: add the lowest bit
void add(int i, int x)
{
for (; i <= N; i += i & -i)
bit[i] += x;
}Changing a[i] must change every cell whose stretch contains i. The first is bit[i] itself; adding the lowest bit jumps to the next cell whose longer stretch also reaches back over i. add(4, 4) writes 4 (0100), then 8 (1000), then 16 is past the end. At most log₂ n + 1 cells change. Building the tree is n of these adds, one per value, which is how the program fills bit in the clip.
bit: 5 7 7 15 4 12 3 36
prefix(7) = 30 in 3 hops
bit: 5 7 7 19 4 12 3 40
after add(4, 4): prefix(7) = 34Range sums
The sum of a[i] to a[j] is prefix(j) − prefix(i − 1), as with Prefix sums, except that now an update is cheap too.
Against a segment tree
A segment tree does the same jobs, and a Fenwick tree is smaller and simpler: n cells instead of 2n, and two loops of two lines each. The price is that its range sum takes one prefix away from another, so it works only for operations that can be undone by subtraction, such as sums and counts. A minimum cannot be subtracted out, and needs the segment tree.
Running it yourself
gcc -std=c11 -Wall -Wextra -pedantic fenwick.c -o fenwick
./fenwickWorked example
A range. a[3] to a[6] is prefix(6) − prefix(2). prefix(6) reads 6 then 4: 12 + 15 = 27. prefix(2) reads 2: 7. The sum is 27 − 7 = 20, which is 7 + 1 + 4 + 8.
prefix(5). 5 (0101) then 4 (0100), then 0: 4 + 15 = 19.
add(3, x). 3 (0011), then 3 + 1 = 4 (0100), then 4 + 4 = 8 (1000): three cells.
Which cells does prefix(8) read? Only cell 8: 1000 has one 1 bit, and clearing it leaves 0.
What is 12 & −12? 12 is 1100; its lowest 1 bit is 0100, 4.
Where it’s used
Changing frequency tables. As scores arrive, a Fenwick tree indexed by score counts them, and the number of scores at or below any value is one prefix sum.
Counting inversions. Walking an array and asking how many larger values came before each one is a prefix sum over the values seen so far, n log n in all.
Rankings. An online game’s rank of a player is the count of players with higher scores, kept current as scores change.
Reference card
| Code or idea | Meaning |
|---|---|
i & -i | the lowest 1 bit of i: 6 & −6 = 2 |
bit[i] | the sum of a[i − (i & −i) + 1] to a[i], not a[i] |
| cells from 1 | 0 & -0 is 0, so a loop would not move |
i -= i & -i | prefix(i): clear the lowest bit each hop |
i += i & -i | add(i, x): add the lowest bit each hop |
| at most log₂ n + 1 steps | for a prefix sum or an update |
| prefix(j) − prefix(i − 1) | the sum of a[i] to a[j] |
| n cells, sums only | against a segment tree’s 2n and any associative operation |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian, two’s complement. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.