By Ahto Truu
Fenwick tree (sometimes also called binary indexed tree, or BIT) is a data structure that deserves to be much more well known among software developers.
Invented by Peter M. Fenwick in 1994, it allows updating of elements in an array and computing sums of arbitrary contiguous blocks of the array, both in time proportional to the logarithm of the length of the array. The magic bit is that the tree lives in the same array and does not take any extra memory!
Originally designed to support frequency counting in arithmetic compression, another usage example is mapping between screen positions and row numbers in a table where row heights may change.
Advertisement
