Fenwick tree

Short description: Data structure

Fenwick tree Binary indexed tree
Type	Binomial tree
Invented	1989
Invented by	Boris Ryabko
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(logn) O(logn) Insert O(logn) O(logn)

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 [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ O(\log n) }[/math] time. This is achieved by representing the values as a tree with [math]\displaystyle{ n+1 }[/math] 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 [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ O(\log n) }[/math] 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 an implicit tree where nodes are consecutively numbered, and parent-child relationships are determined by arithmetic on the node indexes.

An important function in this index arithmetic is the least significant set bit, also called the find first set operation. This is the greatest power of two which divides an index [math]\displaystyle{ i }[/math]. This is the power of two (1, 2, 4, 8, ...) and not the exponent (0, 1, 2, 3, ...). It can be efficiently computed in two's complement arithmetic as [math]\displaystyle{ \operatorname{lsb}(i) = i\mathbin\& -i }[/math] (where & denotes bitwise AND).

A Fenwick tree is most easily understood using a one-based array [math]\displaystyle{ A[n] }[/math] with [math]\displaystyle{ n }[/math] values. Using half-open interval syntax, let [math]\displaystyle{ A(i,j] = \{ A[k] \}_{k=i+1}^j, }[/math] the range from [math]\displaystyle{ i }[/math] (exclusive) to [math]\displaystyle{ j }[/math] (inclusive). The corresponding Fenwick array [math]\displaystyle{ F[n] }[/math] stores the range sums [math]\displaystyle{ \textstyle F[i] = \sum A(i-\operatorname{lsb}(i),i] }[/math]. That is, the sum of [math]\displaystyle{ \operatorname{lsb}(i) }[/math] values ending with and including [math]\displaystyle{ A[i] }[/math].

A fictitious node 0 is used in some descriptions, but is never actually accessed and need not be explicitly stored. [math]\displaystyle{ \operatorname{lsb}(0) = \infty, }[/math] but the value is never actually needed. [math]\displaystyle{ F[0] }[/math] may be considered to contain the sum of the empty range [math]\displaystyle{ A(0,0] = \{\} }[/math] with value 0.

A "Fenwick tree" is actually three implicit trees over the same array: the interrogation tree used for translating indexes to prefix sums, the update tree used for updating elements, and the search tree for translating prefix sums to indexes (rank queries). The first two are normally walked upwards, while the third is usually walked downwards.

The interrogation tree

The interrogation tree is defined so that the parent of node [math]\displaystyle{ i }[/math] is [math]\displaystyle{ i - \operatorname{lsb}(i) = i \mathbin\& (i-1) }[/math]. For example, the parent of 6 = 110₂ is 4 = 100₂. Implicit node 0 is the root.

Each level [math]\displaystyle{ k }[/math] of the tree contains nodes with indices corresponding to sums of [math]\displaystyle{ k }[/math] distinct powers of 2 (with [math]\displaystyle{ k=0 }[/math] representing an empty sum 0). For example, level [math]\displaystyle{ k=1 }[/math] contains nodes [math]\displaystyle{ 1=2^0, 2=2^1, 4=2^2, ... }[/math] and level [math]\displaystyle{ k=2 }[/math] contains nodes [math]\displaystyle{ 3=2^1 + 2^0, 5 = 2^2 + 2^0, 6 = 2^2 + 2^1, ... }[/math]

Node [math]\displaystyle{ i }[/math] has [math]\displaystyle{ \log_2(\operatorname{lsb}(i)) }[/math] children ([math]\displaystyle{ i+1, i+2, i+4, ..., i+\operatorname{lsb}(i)/2 }[/math]), and [math]\displaystyle{ \operatorname{lsb}(i) }[/math] total descendants. (These numbers include nodes greater than [math]\displaystyle{ n }[/math], which are omitted and never accessed.)

The below diagram shows the structure of a 16-node Fenwick tree's interrogation tree, including the root, so it corresponds to a 15-element array A:

Depiction of a 16-node Fenwick interrogation tree containing range sums of a 15-node array A

To find the prefix sum [math]\displaystyle{ A[1] + \cdots + A[i] }[/math], sum the values in [math]\displaystyle{ i }[/math], its parent, its parent's parent, and so on up to (but not including) the root. To compute a range sum [math]\displaystyle{ A[i] + \cdots + A[j] }[/math], subtract the prefix sums for [math]\displaystyle{ i-1 }[/math] and [math]\displaystyle{ j }[/math]. This can be optimized by stopping at their first common ancestor.

The update tree

The update tree is the mirror image of the interrogation tree. The parent of node [math]\displaystyle{ i }[/math] is [math]\displaystyle{ i + \operatorname{lsb}(i) = (i \mathbin| (i - 1)) + 1 }[/math] (where | denotes bitwise OR). For example, the parent of 6 = 110₂ is 8 = 1000₂.

This conceptual tree is infinite, but only the part with indexes up to [math]\displaystyle{ n }[/math] is stored or used. Excluding the fictitious nodes with indexes greater than [math]\displaystyle{ n }[/math] it will be a forest of disjoint trees, one for each bit set in the binary representation of [math]\displaystyle{ n }[/math].

Here, a node's ancestors are all nodes whose range sums include its own. For example, [math]\displaystyle{ F[6] }[/math] holds the sum of [math]\displaystyle{ A(4,6] }[/math], [math]\displaystyle{ F[8] }[/math] holds the sum of [math]\displaystyle{ A(4,8] }[/math], and so on.

To modify one of the values [math]\displaystyle{ A[i] }[/math], add the change to [math]\displaystyle{ F[i] }[/math], then [math]\displaystyle{ i }[/math]'s parent, then its grandparent, and so on, until the index exceeds [math]\displaystyle{ n }[/math].

The search tree

Unlike the other two trees, the search tree is a binary tree, arranged in an order Knuth calls a "sideways heap". Each node is assigned a height equal to the number of trailing zeros in the binary representation of its index, with the parent and children being the numerically closest index(es) of the adjacent height. Nodes with odd indexes ([math]\displaystyle{ \operatorname{lsb}(i) = 1 }[/math]) are leaves. Nodes with even indexes have the closest two nodes of the next-lowest index as children, [math]\displaystyle{ i \pm \operatorname{lsb}(i)/2 }[/math]. Node [math]\displaystyle{ i }[/math]'s parent in the search tree is [math]\displaystyle{ (i - \operatorname{lsb}(i)) \mathbin| (2 \cdot \operatorname{lsb}(i)) }[/math].

For example, the children of 6 = 110₂ is are 5 = 101₂ and 7 = 111₂, and its parent is 4 = 100₂.

Although this tree is potentially infinite, we may define its root to be the highest existing node, whose index is the greatest power of 2 less than or equal to [math]\displaystyle{ n }[/math].

It is possible for a node to have a fictitious parent with an index greater than [math]\displaystyle{ n }[/math] yet still have an existing grandparent. If the example above applied to a 5-node tree, then node 5 would have a fictitious parent 6, but an existing grandparent 4.

The search tree may be considered a combination of the previous two trees. A node's left subtree contains all of its descendants in the update tree, while its right subtree contains all of its descendants in the interrogation tree. A node's parent in the search tree is either its interrogation or update parent (depending on whether the node is a right or left child, respectively), and the other type of parent may be found by multiple upward steps in the search tree.

However, upward traversals in the search tree are uncommon; its primary use is to perform rank queries: given a prefix sum, at what index does it appear? This is done by a downward traversal through the search tree. During the traversal, three variables are maintained: The current node's index, the rank being sought in the subtree rooted and the current node, and a "fallback index" to be returned if the rank sought is greater than can be found in the subtree.

Initially, the current node is the root, the rank sought is the original query, and the fallback index is a special "overflow" value indicating that the rank is not in the tree. (Depending on the application, [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ n+1 }[/math] might be used for this purpose.)

Each step, either the current node is a fictitious node (index greater than [math]\displaystyle{ n }[/math]), or we must decide if the position sought is to the left or right of the end of the current node. If the rank sought is less than the Fenwick array value [math]\displaystyle{ F[i] }[/math] for the current node, we must search its left subtree. If it is greater, search its right subtree. If it is equal, the direction chosen depends on how you wish to handle searches for sums lying exactly between two nodes.

These three possibilities are then further divided based on whether the current node is a leaf or not:

• If the current node is a leaf and:
  • the target is in its (empty) left subtree, return the current index.
  • it is fictitious or the target is in its right subtree, return the fallback index.
• If the current node is not a leaf and:
  • it is fictitious, search for the same rank in its left subtree with an unchanged fallback index.
  • the target is in its left subtree, search for the same rank in its left subtree with the current index as the fallback index.
  • the target is in its right subtree, search for the target rank minus the current node's value in the right subtree, with an unchanged fallback index.

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 -= lsb(index)
    return sum

function update(tree, index, value) is
    while index < size(tree) do
        tree[index] += value
        index += lsb(index)

The function [math]\displaystyle{ \text{lsb}(n) }[/math] computes the least significant 1-Template:Wjbit or last set bit of the given [math]\displaystyle{ n }[/math] or, equivalently, the largest power of two that is also a divisor of [math]\displaystyle{ n }[/math]. For example, [math]\displaystyle{ \text{lsb}(20) = 4 }[/math], as shown in its binary representation: [math]\displaystyle{ \text{lsb}(10\textbf{1}00_2) = 100_2 = 4 }[/math]. This function can be simply implemented in code through a bitwise AND operation: lsb(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 [math]\displaystyle{ O(n\log{n}) }[/math] time, but an [math]\displaystyle{ O(n) }[/math] construction is possible:

function construct(values) is
    tree := values
    for every index, value in tree do
        parentIndex := index + lsb(index)
        if parentIndex < size(tree) then
            tree[parentIndex] += value
    return tree

See also

• Order statistic tree
• Prefix sums
• Segment tree

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