Fenwick Tree or Binary Indexed Tree(BIT)
We are given an array a[], and we want to be able to perform two types of operations on it. Change the value stored at an index i. (This is called a point update operation) Find the sum of a prefix of length k. (This is called a range sum query) Solving this question using brute force method would result in a time complexity of O(k) for finding the sum. Using segment tree the same can be done in O(logK) time. How much better can BIT do to the time complexity? Ans: No Better.. Time complexity will be same as O(logK) Then why use it? Ans: B ecause binary indexed trees require less space and are very easy to implement during programming contests (the total code is not more than 8-10 lines ). We know the fact that each integer can be represented as sum of powers of two. Similarly, for a given array of size N, we can maintain an array BIT[] such that, at any index we can store sum of some numb...