Efficient data aggregation with Fenwick trees

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.





Your Privacy

By clicking "Accept Non-Essential Cookies" you agree ACCU can store non-essential cookies on your device and disclose information in accordance with our Privacy Policy and Cookie Policy.

Current Setting: Non-Essential Cookies REJECTED


By clicking "Include Third Party Content" you agree ACCU can forward your IP address to third-party sites (such as YouTube) to enhance the information presented on this site, and that third-party sites may store cookies on your device.

Current Setting: Third Party Content EXCLUDED



Settings can be changed at any time from the Cookie Policy page.