Fenwick tree - Wikipedia

submited by

Style Pass

2024-04-25 16:30:09

A Fenwick tree or binary indexed tree (BIT) is a data structure that can efficiently update values and calculate prefix sums in an array of values.

This structure was proposed by Boris Ryabko in 1989[1] with a further modification published in 1992.[2] It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.[3]

When compared with a flat array of values, the Fenwick tree achieves a much better balance between two operations: value update and prefix sum calculation. A flat array of n {\displaystyle n} values can either store the values or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array values requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both 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 the value of each node in the tree is the prefix sum of the array from the index of the parent (inclusive) up to the index of the node (exclusive). 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. The tree structure allows the operations of value retrieval, value update, prefix sum, and range sum to be performed using only O ( log ⁡ n ) {\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, in addition to allowing changes to the underlying value array and having all further queries reflect those changes.