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 ${\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 ${\displaystyle O(\log n)}$ time, but requires ${\displaystyle O(n)}$ time to update one of the values.

A Fenwick tree allows all three operations to be performed in ${\displaystyle O(\log n)}$ time. This is achieved by representing the values as a tree with ${\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 ${\displaystyle n}$ values, with the implicit root node omitted from the array. The tree structure allows the operations of value retrieval, value update, prefix sum, and range sum to be performed using only ${\displaystyle O(\log n)}$ node accesses.

Given an array of values, it is sometimes desirable to calculate the running total of values up to each index according to some associative binary operation (addition on integers being by far the most common). Fenwick trees provide a method to query the running total at any index, or prefix sum, while allowing changes to the underlying value array and having all further queries reflect those changes.

Fenwick trees are particularly designed to implement adaptive arithmetic coding, which maintains counts of each symbol produced and needs to convert those to the cumulative probability of a symbol less than a given symbol. Development of operations it supports were primarily motivated by use in that case.^{[citation needed]}

A Fenwick tree is an implicit tree where nodes are consecutively numbered, and parent-child relationships are determined by arithmetic on the node indexes.