Fenwick tree

A Fenwick tree or binary indexed tree (BIT) is a data structure that stores an array of values and can efficiently compute prefix sums of the values and update the values. It also supports an efficient rank-search operation for finding the longest prefix whose sum is no more than a specified value. Its primary use is operating on the cumulative distribution function of a statistical frequency table which is updated often.

This structure was proposed by Boris Ryabko in 1989

with a further modification published in 1992.

It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.

A simple array of values is trivial (constant-time) to update but requires

O

(

n

)

{\displaystyle O(n)}

time to compute a prefix sum or search for a prefix length.

An array of prefix sums can return a prefix sum in constant time, and search for a prefix length in

O

(

log

⁡

n

)

{\displaystyle O(\log n)}

time, but requires

O

(

n

)

{\displaystyle O(n)}

time to update one of the values.

A Fenwick tree allows all three operations to be performed in

O

(

log

⁡

n

)

{\displaystyle O(\log n)}

time. This is achieved by representing the values as a tree with

n

+

1

{\displaystyle n+1}

nodes where each node in the tree stores the sum of the values from the index of its parent (exclusive) up to the index of the node (inclusive). The tree itself is implicit and can be stored as an array of

n

{\displaystyle n}

values, with the implicit root node omitted from the array.