Can any one please explain about Binary index tree and segment tree.I have tried to understand topcoder turorial but I could not understand.So any one please give resources which are easy to understand. asked 17 Jul '14, 14:18

Binary Index Tree (BIT) is used to store prefix sum i.e. sum of numbers from first element to a given point. Consider this question : Your task is to print sum of numbers in an array in a given interval (say 4th to 9th element) and to add a number to a given index(say 5th element). approach 1 : You can store numbers from 1st element to given index. e.g. say arr[]={2,4,6,8}; you can store sum as sum[]={2,4+2,6+4+2,8+6+4+2}. In this approach finding sum is done in constant time.(e.g. sum of elements between 2nd and third element is sum[2]sum[0]). But updating operation will take O(n) time. If second operation is more in test case, this approach will give TLE. approach 2 : Store the difference between two numbers in an array as : sum[]={2,2,2,2}. i.e. sum[i]=arr[i+1]arr[i]. Here update operation is done in linear time (just add the number to the given index in sum[]). But finding sum will take O(n) time leading to TLE if finding sum is prevalent in the test cases. approach 3 : Use Fenwick tree (a.k.a. BIT). It takes O(logn) time for both sum finding and update operation.
http://community.topcoder.com/i/education/binaryIndexedTrees/BITimg.gif Now how do we implement it ? We will use a mathematical trick. Initially, all the elements of the fenwick_array is set to zero. Then all input_array element is added to it according to the rules mentioned above. When we add a number to a position, we have to add the number to other positions as well (as per the picture). The trick here is, when we add a number to an index, we will add this number to index given by
(Why this is done is explained in topcoder tutorial. First get comfortable with the coding, then try to understand the concept.) We will do this for all the elements in the array.
The retrive operation gives sum of elements from zeroth element to the given element. To find sum between two indices (say 2nd and 4th), use retrive(fenwick,size,4)  retrive(fenwick,size,2). Hope this helps. answered 17 Jul '14, 15:02
@dragonemperor Thanks a lot.
(17 Jul '14, 15:52)

The best resource for studying Binary Index Trees is this topcoder link But this link might not be noob friendly(At least was not in my case). However this is very good for understanding the basics of BIT. When you understand it from the second link then go to the first one and study complete thing 10 times. Binary index trees quite abstruse but very easy to implement and remember. After building an understanding, you can use them as a black box for carrying out a number/type of operations without worrying about the internal mechanisms. Binary index trees(BIT) can be used for a number of operations. Here are the ones I know sorted by difficulty. I'll take example of sum but I think it can be used for any associative operation(With slight modifications). Range Query Point Update(Basic, Most used)
Point Query Range Update(Slightly modified)
Range Query Range Update(Quite modified, Infact 2 BITs are used)
answered 17 Jul '14, 16:26
@nitinj Thanks a lot and kindly will you give resources for Segment tree ?
(17 Jul '14, 16:37)
@nitinj In range update and range query case, we have considered that initially all elements are 0. What if they are not? Expressions of sum will change. Plss help i am unable to understand this. Thanks in advance.
(22 Jul '14, 16:52)

Hi. Have a look at this tutorial for segment tree by Utkarsh Lath. It is considered one of the best tutorials for Seg trees. Code is also pretty simple and easy to understand. Hope it helps answered 17 Jul '14, 19:08
