# Crate fenwick [−] [src]

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

## Modules

array |
Operations on a 1D Fenwick tree stored in a zero-based slice. |

index |
Iterators yielding index sequences for traversing Fenwick trees. |