Fenwick tree

An arithmetic code compresses a text the better, the more accurately it guesses the next word. The model keeps a count for each word of the vocabulary, and at every step the coder needs to know two things: how much all the words that come earlier in the table “weigh”, and how much the word itself weighs. Then the word’s count goes up by one, and the next word is coded by the new table. The vocabulary of War and Peace has 47,585 words: the sum up to a word in the middle of the alphabet is more than twenty thousand additions, and this happens 436 thousand times. Press Play.

Over the first hundred thousand words the coder spends 12.05 bits per word on average, 147.1 KB. A word’s number written out in full takes 15.54 bits: the model saves almost a quarter, because frequent words get wide intervals and a short code. Now look at the counters under the strip. To add up the weights of all the words before the current one, a plain pass over the table makes 21,826 additions on average. The Fenwick tree makes 15.7 steps per word, for the sum and for adding one together. Switch to Letters: the alphabet of the novel has 33 letters and a space, a pass costs 15 additions, and no tree is needed. Letter by letter, incidentally, comes to 27 bits per word, more than twice as much, though the word model got its vocabulary for free.

The idea

Cell number i holds the sum of the block of elements that ends at i and has length i & −i, the lowest one bit of i. The sum of the first i elements is cell i, then cell i without its lowest one bit, and so on down to zero: the blocks lie end to end from right to left. Adding to element s means updating all the cells whose blocks contain it: s, s plus its lowest one bit, and so on. Neither path is longer than the number of binary digits in n.

The blocks come out like this. For odd numbers the lowest one bit is one itself: cells 1, 3, 5, 7 hold one element each. Cells 2, 6, 10, 14 hold pairs, 4 and 12 fours, 8 an eight, 16 all sixteen. Numbering starts from one: zero has no lowest one bit. Below are sixteen cells over the word lengths of the novel: column k is words of k letters, the last one words of sixteen letters and longer.

Click column 13. In binary 13 is 1101. Cell 13 holds one column, cell 12 = 1100 holds columns 9–12, cell 8 = 1000 holds columns 1–8. Together that is exactly columns 1–13, and the sum is put together from three numbers. Now add words with the “+1 word” button: if a word has four letters, the one goes to cells 4 = 00100, 8 = 01000 and 16 = 10000, all the blocks that contain column 4. The sum path removes the lowest one bit, the update path adds it. That is the whole structure; the operation i & −i is taken apart in the article on bit tricks.

No tree is drawn here, but there is one: the parent of cell i on the update path is cell i plus its lowest one bit, and its block begins at the same place or further left and ends further right. Hence the name binary indexed tree, a tree indexed by binary numbers. There are no pointers and no extra cells: an array as long as the data.

Why log n steps are enough

A sum takes as many steps as there are ones in the binary notation of the number; an update at most as many as there are zeros above the lowest one bit, plus one. In the vocabulary coder the numbers are 16-bit, and the sum and the addition together take 15.7 steps per word.

The tree can be built in O(n) rather than with n updates: each cell, once its sum is ready, adds it to cell i + lowbit(i), its parent. If all the counts are one, as at the start of the coder’s work, cell i holds exactly lowbit(i).

Whose sum is this

The decoder needs the opposite question. It knows a point on the strip, a number from zero to the total, and has to find the word whose interval covers it: the smallest s for which the sum of the first s + 1 counts is greater than the point. One could binary search over prefix sums, but that is O(log² n). A Fenwick tree allows a descent in O(log n): go over the powers of two from the top down and try to step 2^k forward. The cell we land in holds exactly the block between the old position and the new one, because the new position is a multiple of 2^k and the old one a multiple of 2^k+1. If the whole block is less than what remains of the point, step and subtract it; otherwise keep the position and try a step half as long.

Click the strip in the first scene: the descent checks 17 powers of two and finds the word. The decoder in the listing below recovers all 100,000 words this way from the interval starts alone, spending 25.2 steps per word on the descent and adding one. The same descent finds the k-th order statistic: the “The median length” button in the second scene looks for the word that stands in the middle if all the words are lined up by length.

Counts for an arithmetic code

In 1987 Ian Witten, Radford Neal and John Cleary published a detailed implementation of arithmetic coding in C in Communications of the ACM. Their adaptive model keeps the counts of 257 symbols, the bytes and end of file, together with the cumulative sums, and the authors say plainly that updating the model is expensive: the sums have to be maintained after every symbol. To make the pass shorter they keep the table ordered by frequency, like a self-organising list: frequent symbols end up at the start. For bytes this is enough. For words it is not: even if the table of War and Peace were ordered by frequency in advance, the pass up to a word would cost 4098 additions on average.

In 1989 Boris Ryabko described the same structure, sums in blocks by powers of two, in a paper on a fast adaptive code. In 1994 Peter Fenwick published it in the journal Software: Practice and Experience in the paper “A new data structure for cumulative frequency tables”, called it a binary indexed tree, and under Fenwick’s name it spread through textbooks and olympiads. Both had the same reason: arithmetic coding with changing frequencies.

Code

A coder and decoder of War and Peace by words. The model knows the vocabulary of the novel in advance (a coder would not get to send it for free), and learns the frequencies as the text goes on. Instead of the arithmetic code itself the program computes its ideal length: log₂(total / word count) bits per word. An arithmetic code with exact arithmetic is longer than this sum by at most two bits over the whole text; real coders with finite precision lose a little more. The coder remembers the start of each word’s interval, and the decoder recovers the text from these numbers by the descent.

first 100000 words: 12.049 bits per word, 147.1 KB
steps per word: tree 15.7, plain table 21826
decoded back: every word matches; first words: лев толстой том первый часть первая

The program computes the code length for the whole novel without the tree: it depends only on the counts, not on where the word stands in the table: 11.692 bits per word, 622.4 KB. The tree is needed to produce the code itself, the start of each word’s interval.

A Fenwick tree generalises naturally to two coordinates: cell (i, j) holds the sum of a rectangular block, and the paths over the two coordinates nest one inside the other. Below, all 19,073 earthquakes of magnitude five and above from 2015 to 2025 go onto a one-degree grid: after each year the program asks how many had happened by then in three rectangles of the map. Each event takes 18.8 steps, each rectangle four sums from a corner, 50.7 steps, while the grid has 64,800 cells.

What it costs

Memory is n + 1 numbers, exactly as many as the data. The benchmark is that very step of the coder, the sum up to a symbol and adding one, on alphabets from 16 to half a million symbols: a plain table, a Fenwick tree and a bottom-up segment tree, which can do the same.

On sixteen symbols the plain table in Python is faster than the tree: the slice is summed in C. At 128 they are level, and at half a million symbols the table is 540 times slower in Python and 1440 times slower in Go. The segment tree in this race is 1.6–2 times slower than Fenwick in Python and 1.7–3 times in Go: the Fenwick path is one variable and one bit operation per step, while the segment tree gathers the sum from both ends and holds twice as many cells.

What it cannot do

The sum of a range is the difference of two prefixes, and this works for any operation that has an inverse: addition, exclusive or, multiplication modulo a prime. The minimum on an arbitrary range cannot be had this way: a Fenwick tree can hold the minimum of a prefix, but a minimum cannot be “subtracted”. If you need the minimum on a range, take a segment tree or, if the data does not change, a sparse table.

Ranges, on the other hand, can be handled with a trick through differences, as in a difference array. If the tree holds the differences of neighbouring elements, adding to a range [l, r] is two updates, at l and at r + 1, and the value of an element is a prefix sum. Two such trees together give both adding to a range and the sum of a range. Assigning a value to a range cannot be expressed this way: it needs the lazy operations of a segment tree.

Another common technique is counts by value. If position v of the tree holds the number of elements already seen with value v, a prefix sum answers how many of them are smaller than a new one: that is the rank of the new element and the number of inversions it creates. Values up to a billion are first compressed to indices. The fast version of the longest increasing subsequence works the same way, with maximum instead of sum: a maximum over a prefix needs no inverse operation.

Problems

In the first problem each new earthquake from the USGS catalogue has to be put in its place among all the previous ones: counts over compressed values. In the second you write the decoder of an adaptive code and recover the beginning of War and Peace from the interval starts: a descent in the tree.