Fenvick Tree
Fenwick Tree aka Binary Indexed Tree (BIT) is a data structure which can handle Range Sum Queries very easily. The advantage it has over the segment trees, which is another data structure which is used for range queries, is that it has a less complicated implementation than the segment trees.The data structure itself is implemented on array The idea is that each of the element in fenvick tree is responsible for storing the sum of fixed set of elements in the original array. If m is th largest integer s.t. 2 m divides i then FT i = A i-1 +A i-2 +...+A i-2 m For eg as illustrated in the figure FT 6 = A 5 +A 4 (since 6 is divisible by 2 it will store sum of 2 elements) FT 12 = A 11 +A 10 +A 9 +A 8 (since 12 is divisible by 4) Lets define some terms for the Fenvick Tree ...