Crate fenwick

A Fenwick tree or binary indexed tree/bit indexed tree is a data structure that supports the following two operations efficiently over an array of numbers a[0..n]:

• Calculate a prefix sum: a[0] + a[1] + ... + a[i]
• Update one element: a[i] += delta

With a naïve implementation, only one of the operations can be made to have constant time complexity while the other one has to be linear. With Fenwick tree, both take only O(log(N)).

Get Started

See example in module array which implements a generic 1D Fenwick tree.

Multi-dimensional Fenwick trees can be easily implemented using the building blocks in module index ond a multi-dimensional array (again of the same size/shape as the original).

How it works

A Fenwick tree is implemented as an implicit data structure using an array f of the same length as the original array a. Each node in the tree is represented as an element in f, which stores the sum of a certain subset of elements in a. The operations can then be implemented as follows:

• Prefix sum is calculated by summing a subset of nodes in the implicit tree.
• Updating a element involves updating all nodes in the implicit tree that covers it.

The algorithms for computing "which nodes adds up to a prefix" and "which nodes cover this element" are based on the binary representation of input index and are exposed in module index.

References

• Original Paper
• Tutorial on Topcoder

Modules

array	Operations on a 1D Fenwick tree stored in a zero-based slice.
index	Iterators yielding index sequences for traversing Fenwick trees.