Need resources for Binary index tree, Segment tree

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.

1 Like

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.

    Basically all we are doing is storing sum of numbers as follows :

        1) if array index is of the form 2^n, it stores sum from first element to 2^n th element.
        2) Other odd index stores only the number (no sum).
        3) Even positions stores numbers which is a bit random. (Don't worry about it now).

   Take a look at this picture from top coder : 

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

       index=index+(index & -index)   

(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 code is : 

     void add(int fenwick[],int size,int number,int index)
     {
         while(index<=size)
         {
               fenwick[index]=number;
               index=index+(index & -index);
         }
     }
The retrive operation is just the opposite. We add numbers in add() in forward direction. Similarly, retrive is done in backward direction. Take a look at the code :

     void retrive(int fenwick[],int size,int index)
     {
         int sum=0;
         while(index>0)
         {
               sum=sum+fenwick[index];
               index=index-(index & -index);
         }
     }

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.

7 Likes

@dragonemperor Thanks a lot.

The best resource for studying Binary Index Trees is this topcoder link-

[Topcoder tutorial BIT][1]

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.

[Intuition behind BIT][2]

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)

int read_bit(int* bit, int n, int idx){
    int answer = 0;
    while(idx>0){
        answer += bit[idx];
        idx -= (idx & -idx);
    }
    return answer;
}
void update_bit(int *bit, int n, int idx, int diff){
    while(idx<=n){
        bit[idx] += diff;
        idx += (idx & -idx);
    }
    return;
}

[3]

 1. Read[1,L] - Get prefix sum. This is prefix query i.e you query in a range [1,L] (Both closed brackets because bit works with 1-index array indices).
 2. Read[L,R] - Get sum in range [L,R]
 3. Update[i] - Update the value stored at index i. This operation will update the entries stored in the tree.

**Point Query Range Update(Slightly modified)**

[Basic Tutorial][4]



[5]

  1. Read[i] - Gives you the value at index i(Remember this is different from RQPU in the sense that it only gives value stored at a particular index and not prefix sum for that index)
  2. Update[L,R,X] - Update all values in a range. Either add X to all or subtract X from all values.

Range Query Range Update(Quite modified, Infact 2 BITs are used)

[Basic Tutorial][6]


[7]

[Code and explaination][8]

 1. Read[L,R]- Gives you the sum of values in range[L,R].
 2. Update[L,R,X] - Updates all values stored in the range [L,R]


  [1]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
  [2]: http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a
  [3]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
  [4]: http://zobayer.blogspot.in/2013/11/various-usage-of-bit.html
  [5]: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
  [6]: http://zobayer.blogspot.in/2013/11/various-usage-of-bit.html
  [7]: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
  [8]: http://apps.topcoder.com/forums/?module=RevisionHistory&messageID=1407869
3 Likes

@nitinj Thanks a lot and kindly will you give resources for Segment tree ?

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

1 Like

@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.