Ponder over the below problem
- How to get the sum of m to n index in an array in < O(n) performance. Note 0 <= m < n <= length of array. Think of RLE (Run Length Encoding) problem.
Example – [5,10,15,20,25]. Sum from 0 to 2nd index is 30 (5 + 10 + 15).
Typical solution is to run a loop computing sum for every index and replacing the value with the sum. Sum(n) = Sum (n-1) + value(n). This takes O(n). Binary Indexed Tree solves this with O(log n).
Solution steps
- Construct binary tree out of the given array. Note that the binary tree representation is logical but the underlying data structure is array. Remember how – if the parent node is stored at index i, the left child can be calculated by 2 * i + 1 and right child by 2 * i + 2. Level order traversal used to construct array from the tree.
- Update the values of each nodes by taking sum of all of its left sub tree. This representation is called Binary Indexed Tree.
Now, how we solve the above given problem – Start from root, navigate to the required index. Along the way, keep adding the value of node that comes in the right link. Finally, add the value of the index node with it. There you have the required sum with O(log n) complexity.
References