Fenwick tree

A Fenwick tree or binary indexed tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values. It was proposed by Peter Fenwick in 1994.^[1] Fenwick trees primarily solve the problem of balancing prefix sum calculation efficiency with element modification efficiency. The efficiency of these operations comes as a trade-off - greater efficiency in prefix sum calculation is achieved by pre-calculating values, but as more values are pre-calculated more must be re-calculated upon any modification to the underlying value table. Fenwick trees both calculate prefix sums and modify the table in $O(\log n)$ time, where $n$ is the size of the table.

Description

Given a table of elements, it is sometimes desirable to calculate the running total of values up to each index according to some associative binary operation (addition on integers, for example). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value table and having all further queries reflect those changes. Although Fenwick trees are trees in concept, in practice they are implemented using a flat array analogous to implementations of a binary heap. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each index contains the pre-calculated sum of a section of the table, and by combining that sum with section sums encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all section sums which contain the modified value are in turn modified during a similar traversal of the tree. The section sums are defined in such a way that queries and modifications to the table are executed in asymptotically equivalent time - $O(\log n)$ in the worst case.

The initial process of building the Fenwick tree over a table of values runs in $O(n \log n)$ time. Other efficient operations include locating the index of a value if all values are positive, or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in $O(n)$ time. The sum of an arbitrary subarray can also be calculated by subtracting the prefix sum before its start point from the prefix sum at its end point.

Applications

Fenwick trees are used to implement the arithmetic coding algorithm. Development of operations it supports were primarily motivated by use in that case.

Using a Fenwick tree it is very easy to generate the cumulative sum table. From this cumulative sum table it is possible to calculate the summation of the frequencies in a certain range in order of $O(\log n)$.

Fenwick tree can also be used to update and query subarrays in multidimensional arrays with complexity $O(2^d \log ^d n)$, where d is number of dimensions and n is the number of elements along each dimension. ^[2]

Implementation

A simple C implementation follows.

int A[SIZE];

int sum(int i) // Returns the sum from index 1 to i
{
    int sum = 0;
    while(i > 0) 
        sum += A[i], i -= i & -i;
    return sum;
}
 
void add(int i, int k) // Adds k to element with index i
{
    while (i < SIZE) 
        A[i] += k, i += i & -i;
}

See also

• Order statistic tree
• Prefix sums
• Segment tree

References

1. Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience 24 (3): 327–336. doi:10.1002/spe.4380240306.
2. Pushkar Mishra (2013). "A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays".

External links

• A tutorial on Fenwick Trees on TopCoder
• An article on Fenwick Trees on Algorithmist
• An entry on Fenwick Trees on Polymath wiki