Fenwick tree

The interrogation tree

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

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

Node ${\displaystyle i}$ has ${\displaystyle \log _{2}(\operatorname {lsb} (i))}$ children (${\displaystyle i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2}$), and ${\displaystyle \operatorname {lsb} (i)}$ total descendants. (These numbers include nodes greater than ${\displaystyle n}$, 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:

To find the prefix sum ${\displaystyle A[1]+\cdots +A[i]}$, sum the values in ${\displaystyle i}$, its parent, its parent's parent, and so on up to (but not including) the root. To compute a range sum ${\displaystyle A[i]+\cdots +A[j]}$, subtract the prefix sums for ${\displaystyle i-1}$ and ${\displaystyle j}$. 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 ${\displaystyle i}$ is ${\displaystyle i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1}$ (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 ${\displaystyle n}$ is stored or used. Excluding the fictitious nodes with indexes greater than ${\displaystyle n}$ it will be a forest of disjoint trees, one for each bit set in the binary representation of ${\displaystyle n}$.

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

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

The search tree

Unlike the other two trees, the search tree is a binary tree, arranged in an order Knuth calls a "sideways heap". ^[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. Nodes with odd indexes (${\displaystyle \operatorname {lsb} (i)=1}$) are leaves. Nodes with even indexes have the closest two nodes of the next-lowest index as children, ${\displaystyle i\pm \operatorname {lsb} (i)/2}$. Node ${\displaystyle i}$'s parent in the search tree is ${\displaystyle (i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))}$.

For example, the children of 6 = 110₂ 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 ${\displaystyle n}$.

It is possible for a node to have a fictitious parent with an index greater than ${\displaystyle n}$ 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 indicating that the rank is not in the tree. (Depending on the application, ${\displaystyle 0}$ or ${\displaystyle n+1}$ might be used for this purpose.)

Each step, either the current node is a fictitious node (index greater than ${\displaystyle n}$), 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 ${\displaystyle F[i]}$ 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.

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 ${\displaystyle O(n\log {n})}$ time, but an ${\displaystyle O(n)}$ construction is possible: ^[6]

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