A binary indexed tree is used to efficiently answer prefix sum queries. It takes space, where 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 of the input array, then the binary indexed tree needs to be updated. Suppose that is added to the value at in the input array. To update the binary indexed tree, go to index :
Go to the index in the binary indexed tree. Add 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 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 to :
The following illustration shows how to obtain a prefix sum from index to of the input array.
View all Courses