Binary Indexed Trees (Fenwick Tree)

from: http://algorithmsandme.in/2015/02/binary-indexed-trees/

Why Binary Indexed Tree?

Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is “sum” :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum[5] – sum[1].

[Read More...]