Fenwick tree

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.

A Fenwick tree is most easily understood by considering a one-based array ${\displaystyle A[n]}$ with ${\displaystyle n}$ values. The corresponding Fenwick tree has ${\displaystyle n+1}$ nodes with an implicit node 0 at 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},...}$ The parent of a given node can be found by clearing the last set bit (LSB) in its index, corresponding to the smallest power of 2 in its sum. For example, the parent of 6 = 110₂ is 4 = 100₂.

The below diagram shows the structure of a 16-node Fenwick tree, corresponding to a 15-element array A:

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

Let ${\displaystyle A(i,j]=\{A[k]\}_{k=i+1}^{j}}$. The value of a node at index ${\displaystyle i}$ corresponds to the range sum of values in ${\displaystyle A(\mathrm {parent} (i),i]}$, that is, the values of A starting after the parent's index up to the current node's index, inclusive. The values ${\displaystyle A(\mathrm {parent} (i),i]}$ are considered to be the "range of responsibility" for the current node, and consist of ${\displaystyle \mathrm {lsb} (i)=(i\ \&\ (-i))}$ (where & denotes bitwise AND) values. Note that the indices in this range do not directly correspond to children of ${\displaystyle i}$: for example, the range of responsibility for node 2 is ${\displaystyle A(0,2]=\{A[1],A[2]\}}$ but node 1 is not a child of node 2. The root node 0 contains the sum of the empty range ${\displaystyle A(0,0]=\{\}}$ with value 0.

The initial process of building the Fenwick tree over an array of values runs in ${\displaystyle O(n\log n)}$ time.

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

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

The function ${\displaystyle {\text{lso}}(n)}$ computes the least significant 1-⁠bit or last set bit of the given ${\displaystyle n}$ or, equivalently, the largest power of two that is also a divisor of ${\displaystyle n}$. For example, ${\displaystyle {\text{lso}}(20)=4}$, as shown in its binary representation: ${\displaystyle {\text{lso}}(10{\textbf {1}}00_{2})=100_{2}=4}$. This function can be simply implemented in code through a bitwise AND operation: lso(n) = n & (-n), assuming a signed integer data type.[3]

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

• Order statistic tree
• Prefix sums
• Segment tree

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