What is a binary indexed tree?

A binary indexed tree is used to efficiently answer prefix sum queries. It takes $O(n)$ space, where $n$ is the size of the input array.

Construction

Take a look at the important facts below:

1. The binary indexed tree will take $n+1$ nodes.
2. Each binary tree node contains an index and a value. The value is a prefix sum.

The following illustration explains how a binary indexed tree is created. An indexed binary tree can be represented as an array or a tree. For simplicity, we will represent it as a tree.

To obtain the parent of a node with index i:

1. Covert i to binary.
2. Flip the rightmost bit containing 1 to 0.

For all nodes with an index greater than zero:

1. Express the index in terms of the sum of powers of 2.
2. The first element in the expression denotes the index in the original array from which we need to start computing the sum.
3. The last element in the expression denotes the number of input array elements that need to be included.

Update

If there is a change made at index $i$ of the input array, then the binary indexed tree needs to be updated. Suppose that $x$ is added to the value at $i$ in the input array. To update the binary indexed tree, go to index $i + 1$:

1. Go to the index $m+1$ in the binary indexed tree. Add $x$ to the value in this node.

2. Find the next index to update in the indexed binary tree by finding current index + (current index & (-current index)). Add $x$ to the value in this node and repeat this step until the new index is greater than the number of nodes in the indexed binary tree.

Obtaining the prefix sum

To find the sum of a prefix from $0$ to $m$:

1. Let answer = 0. Go to the index $m+1$ in the binary indexed tree.
2. Traverse from this node to its parent node and add this value to the variable answer.
3. Keep traversing until you reach the parent node and keep adding the values (to the variable answer) in the nodes encountered.

The following illustration shows how to obtain a prefix sum from index $0$ to $2$ of the input array.