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.
Take a look at the important facts below:
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:
For all nodes with an index greater than zero:
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$:
Go to the index $m+1$ in the binary indexed tree. Add $x$ to the value in this node.
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.
To find the sum of a prefix from $0$ to $m$:
The following illustration shows how to obtain a prefix sum from index $0$ to $2$ of the input array.
RELATED TAGS
View all Courses