Fenwick tree on arvau

Wikipedia / Fenwick tree

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.

time to compute a prefix sum or search for a prefix length.

time to update one of the values.

time. This is achieved by representing the values as a tree 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 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, 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.

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. This is the greatest power of two. 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 (where & denotes bitwise AND).

A Fenwick tree is most easily understood using a one-based array values. Using half-open interval stores the range sums.

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

. For example, the parent of 6 = 1102 is 4 = 1002. Implicit node 0 is the root.

, 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:

and update i := i - lsb(i).

The update tree

(where | denotes bitwise OR). For example, the parent of 6 = 1102 is 8 = 10002.

, and so on.

The search tree

Unlike the other two trees, the search tree is a binary tree, arranged in an order Knuth calls a "sideways heap"..

For example, the children of 6 = 1102 are 5 = 1012 and 7 = 1112, and its parent is 4 = 1002.

Although this tree is potentially infinite, we may define its root to be the highest existing.

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 at 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 might be used for this purpose.)

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)

computes the least significant set bit or, equivalently, the largest power of two. This function can be simply implemented in code through a bitwise AND operation: lsb(n) = n & (-n), assuming two's complement negation.

Construction

construction is possible:

function construct(values) is
    tree := values
    for index from 1 to size(tree) do
        parentIndex := index + lsb(index)
        if parentIndex < size(tree) then
            tree[parentIndex] += tree[index]
    return tree