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[1] with a further modification published in 1992.

[3] A simple array of values is trivial (constant-time) to update but requires

A Fenwick tree allows all three operations to be performed in

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

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.

Development of operations it supports were primarily motivated by use in that case.

[citation needed] A Fenwick tree is an implicit tree where nodes are consecutively numbered, and parent-child relationships are determined by arithmetic on the node indexes.

A Fenwick tree is most easily understood using a one-based array

A fictitious node 0 is used in some descriptions, but is never actually accessed and need not be explicitly stored.

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: To find the prefix sum

This conceptual tree is infinite, but only the part with indexes up to

it will be a forest of disjoint trees, one for each bit set in the binary representation of

[5] 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.

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

It is possible for a node to have a fictitious parent with an index greater than

If the example above applied to a 5-node tree, then node 5 would have a fictitious parent 6, but an existing grandparent 4.

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?

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 indicating that the rank is not in the tree.

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

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: A simple pseudocode implementation of the two main operations on a Fenwick tree—query and update—is as following: The function

This function can be simply implemented in code through a bitwise AND operation: lsb(n) = n & (-n), assuming two's complement negation.

[3] One naïve algorithm to construct a Fenwick tree consists of initializing the tree with null values and updating each index individually.