BIT ALGORITHM

if anyone can please explain Binary Indexed Tree algorithm because i’ve read Top Coder tutorial and didnt get it i think it was somehow hard ! if someone can give a detailed explanation . Thanks

6 Likes

@blingo99 Top Coder tutorial is very nice but hard to understand first time
Ok i am giving some key points of BIT algorithm

  1. This is used for Update and Query problems Suppose you have N update and Query So for this Naive Approach have O(n) Complexity for update and O(1) For Query for Query.

  2. By using this algorithm you can solve both problem in O(logN) time.

  3. In this algorithm you have to create one Tree that store the previous values.

  4. You have 2 Function in this algorithm one for Update and another for Query.

Update Function is :

void update(int idx, int val)  // idx is the index of element that you have to update
{
        while (idx <= maxVal)
        {
                 tree[idx] += val;   // for this you have update total tree
                 idx += (idx & -idx);  // generate indices to update in a tree.
        }
}

Query Function is :

int query(int idx)  // idx is the index of element 
 {
        int sum=0;
        while (idx>0)
        {
              sum += tree[idx];
              idx -= (idx & -idx); // change the index of tree .
        }
        return sum;
  }

the above two functions used for a specific problem:
You have N elements and you have to find the sum in a range say i…j as a Query

You have to update arr[x] as a update.

May this will help you If you have any Query ask me.

Happy Coding!!!

11 Likes

@blingo999: no u have to call update only two times. For sake let u have to update range i to j by adding value x. then call update two times with parameters: update(i,x) and update(j+1, -x). Go through this simple problem of BIT codechef.com/problems/SPREAD

3 Likes

@upendra: how to use BIT for the problems like:
There are N cards(all face up) on table we have 2 types of queries:

  1. Turn i j (turn cards from i to j both inclusive)
  2. Q i j (how many cards b/w i and j are faced up)

Can u sort out this problem?

2 Likes

why u did idx-=(idx&-idx);
plzz explain!!i m still not getting!!Thanx

1 Like

the operation idx-=(idx&-idx) sets the last bit of the index to 0.

For example if idx=12 the binary representation is 1100…so it gets changed to 1000 ie 8.Hope this helps.

2 Likes

@jaythegenius I try to make some things clear about BIT. BIT is a kind of range tree as u know like a segment tree but it works differently.

For eg u make a query for index 5(101) so the BIT will give u the answer for ur query from 0 to 5.
Now the whole information is not stored only at index 5 in BIT but also at all those indexes which we get by one by one unsetting the set bit from it from left.

So 5(101) becomes 4(100) and then 0(000).As we encounter 0 we stop.
Now to do this thing we are doing idx-=(idx&-idx)

Now its complexity for a query is O(logn) coz thats the maximum set bits.

4 Likes

I think after reading above you know the difference btw BIT and segment tree but to experience it practically be free to go through the question.

1.http://www.codechef.com/problems/SPREAD
This question will surely make you understand the difference b/w BIT and segmented tree…just try to implement it using both.

2.Also read the tutorial at topcoders for BIT and to understand the lazy propogation (SEGMENTED TREES)…just tap the link shown below :
http://p–np.blogspot.in/2011/07/segment-tree.html

I hope now you will feel better …Happy coding…Also if you come to know about some other tricky question be frank to tell me…:)…:smiley:

3 Likes

Can we use BIT to get sum in ranges? If yes then how?

http://codeforces.com/blog/entry/619

this is one of the best tutorials in BIT . if u dont have any Idea of BIT , Go through it , you will easily understand the basics

1 Like

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8917&rep=rep1&type=pdf

this research paper has got great explanation.

1 Like

Yes, you can get sum of values at index L to R inclusive.

Check this link for complete tutorial - https://www.hackerearth.com/notes/binary-indexed-tree-made-easy-2/

1 Like

Correct me if i am wrong somewhere …

if i want to update from index i to j will i call the update function j-i times ?!

2 Likes

because let idx=X1Y where X=‘111…’ and Y=‘000…’ thus when we calculate -idx=(idx)’+1 . idx’=X’0Y’ hence it will be look like idx’=000…0111…’ now idx’+1=000…10000 .hence by ANDing it to idx we get the most right 1 bit from idx. idx&(-idx)=0000…10000…

1 Like

@master_pk: Can you please clarify how update(i,j,x) is update(i,x) and update(j+1,-x).

for segment updating point querying how it can be proved that update(u,v,k) = update(u,k) and update(v+1,-k) and how now query§ will give single point query ?

Given a simple 1-d array, how e have to make this BIT??

@damn_me Iterate through each of the array elements and do an ‘update()’. This will construct a BIT.

can you explain how it really do using some demo examples…
thanks