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
- Calculate a prefix sum:
a + a + ... + 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
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).
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
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.
Operations on a 1D Fenwick tree stored in a zero-based slice.
Iterators yielding index sequences for traversing Fenwick trees.