Fenwick tree

Fenwick tree
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
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.
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 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 time. This is achieved by representing the values as a tree with 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 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 node accesses.
Motivation
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.
Fenwick trees are particularly designed to implement the arithmetic coding algorithm, 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.
Description
A Fenwick tree is most easily understood by considering a one-based array with values. The corresponding Fenwick tree has nodes with an implicit node 0 at the root. Each level of the tree contains nodes with indices corresponding to sums of distinct powers of 2 (with representing an empty sum 0). For example, level contains nodes and level contains nodes The parent of a given node can be found by clearing the last set bit (LSB) in its index, corresponding to the smallest power of 2 in its sum. For example, the parent of 6 = 1102 is 4 = 1002.
The below diagram shows the structure of a 16-node Fenwick tree, corresponding to a 15-element array A:
Let . The value of a node at index corresponds to the range sum of values in , that is, the values of A starting after the parent's index up to the current node's index, inclusive. The values are considered to be the "range of responsibility" for the current node, and consist of (where & denotes bitwise AND) values. Note that the indices in this range do not directly correspond to children of : for example, the range of responsibility for node 2 is but node 1 is not a child of node 2. The root node 0 contains the sum of the empty range with value 0.
The initial process of building the Fenwick tree over an array of values runs in time.
Pseudocode
A simple pseudocode implementation of the two main operations on a Fenwick tree—query and update—is as following:
function query(tree, index) is
sum := 0
while index > 0 do
sum += tree[index]
index -= lso(index)
return sum
function update(tree, index, value) is
while index < size(tree) do
tree[index] += value
index += lso(index)
The function computes the least significant 1-bit or last set bit of the given or, equivalently, the largest power of two that is also a divisor of . For example as shown in its binary representation: . This function can be simply implemented in code through a bitwise AND operation: lso(n) = n & (-n), assuming a signed integer data type.
Construction
One naive algorithm to construct a Fenwick tree consists of initializing the tree with null values and updating each index individually. This solution works in time, but an construction is possible:
function construct(values) is
tree := values
for every index, value in tree do
parentIndex := index + lso(index)
if parentIndex < size(tree) then
tree[parentIndex] += value
return tree
See also
Order statistic tree
Prefix sums
Segment tree
References
External links
A tutorial on Fenwick Trees on TopCoder
An article on Fenwick Trees on Algorithmist
An entry on Fenwick Trees on Polymath wiki
stack exchange
Trees (data structures)
Soviet inventions
Russian inventions