Wednesday, November 27, 2013

Various Usage of B.I.T.


I’ve always imagined what BIT (I will omit the dots, but don't confuse it with binary bits) can do and can’t. I have seen numerous times, experienced solvers say “Oh it’s easily solvable using BIT” leaving me wondering, “BIT on this problem! How on earth!” Still I haven’t found quite a good answer for this question. Looks like BIT can do as much as you can imagine it to do (and obviously design it to do so).

However, I am not going to explain the structure of BIT or how it works etc. As there are lots of well documented articles available on the net. I can’t help putting one specific link here, which is a TopCoder algorithm tutorial for BIT. So, if you are not familiar with BIT yet, first go ahead, and read that post.

In this post, we will discuss some of the most common application of BIT for solving data structure related problems, more specifically, where range sum updates and queries are involved.

Some methods used in this post:
Update(x, v): Adds V at the position x in BIT.
Query(x): Returns the cumulative value on position x in BIT.
Read the above tutorial to know how these methods are implemented.
We will be using 1-based indexing throughout the post.

(I) Point Update, Range Query:

This is the most common form of BIT, and just about 99% of online tutorials you will find on the net will describe this application. So here we don't have much to say. If your updates are like “Add v in the x position of the array”, and queries are like “What is the sum of elements in index range [a, b] in the array?”, then all you do for update is call Update(x, v) and answer queries by Query(b) - Query(a-1). Simple cumulative sum formula, nothing really astonishing. This problem is can be solved using BIT: SPOJ - MSE06H.

(II) Range Update, Point Query:

Although not something you see every now and then, but it's readily doable. Now you are required to update v over the range [a, b] and the query is performed on a single index x. So now you call update twice, first add v at index a, then remove v for indices larger than b, which is: Update(a, v); Update(b+1, -v); And for query, you simply call Query(x). Now to see why this works, the following reasoning can be made:

Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, -v). Now what will happen if you call Query(x)? Three cases can arise:
1. if x < a, the query is not affected by the updates. So you get correct result.
2. if x > b, x will be affected by the update(a, v) since x ≥ a, and update(b+1, -v) since x ≥ b+1, therefore, v-v=0 so everything cancels out. Again, you get the correct result.
3. a ≤ x ≤ b. x is only affected by update(a, v), but not update(b+1, -v), therefore, Query(x)'s value is increased by v, and it will return the correct result.

As we can see, in this fashion, we can increment or decrement for a range [a, b], and get a single index effect for some index x. This problem is an example: SPOJ - UPDATEIT

(III) Range Update, Range Query:

I didn't even know it exists until I read some post in TopCoder forums (the post was made by: AnilKishore).

I will just re-state his explanation as it was quite clear itself. All we want here is to support range updates, and do range queries. As from the previous type, if we try to store range updates, the BIT structure effectively captures updates for single positions, instead of range/cumulative sums. However, we can do some tweaking to work around this problem.

Let's just consider only one update: Add v to [a, b] while the rest elements of the array is 0.
Now, consider sum(0, x) for all possible x, again three situation can arise:
1. 0 ≤ x < a : which results in 0
2. a ≤ x ≤ b : we get v * (x - (a-1))
3. b < x < n : we get v * (b - (a-1))

This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it, where:
1. 0 ≤ x < : Sum should be 0, thus, T = 0
2. a ≤ x ≤ : Sum should be v*x-v*(a-1), thus, T = v*(a-1)
3. b < x < n : Sum should be 0, thus, T = -v*b + v*(a-1)

As, we can see, knowing T solves our problem, we can use another BIT to store this additive amount from which we can get:
0 for x < a, v*(a-1) for x in [a..b], -v*b+v(a-1) for x > b.

Now we have two BITs.
To add v in range [a, b]: Update(a, v), Update(b+1, -v) in the first BIT and Update(a, v*(a-1)) and Update(b+1, -v*b) on the second BIT.
To get sum in range [0, x]: you simply do Query_BIT1(x)*x - Query_BIT2(x);
Now you know how to find range sum for [a, b]. Just find sum(b) - sum(a-1) using the formula stated above.

Pretty impressive this one! SPOJ - HORRIBLE can be solved in this approach. And thanks to Iqram Mahmud for this nice problem.

(IV) 2D BIT

How to write Update and Query methods for 2D BIT is well described in the TopCoder tutorial I've mentioned above. The only thing to notice here is how the queries and updates work. 2D BIT is basically a BIT where each element is another BIT. Adding v on (x, y) means it's effect will be found throughout the rectangle [(x, y), (W, H)], and query for (x, y) gives you the result of the rectangle [(0, 0), (x, y)], assuming the total rectangle is [(0, 0), (W, H)]. SO when you query and update on this BIT, you have to be careful about how many times you are subtracting a rectangle and adding it. Simple set union formula works here. So if you want to get the result of a specific rectangle [(x1, y1), (x2, y2)], the following steps are necessary to do so:
V = Query(x2, y2)
V -= Query(x2, y1-1)
V -= Query(x1-1, y2)
V += Query(x1-1, y1-1)

This problem is an example: SPOJ - MATSUM

This page is likely to be updated if I find and manage to solve new types of BIT problems. Please let me know if there are mistakes. This post is inspired by some random posts lying around in TopCoder forums, I just wanted to put them in one place for future reference.


31 comments:

  1. Replies
    1. It's more like an attempt to gather everything at one place. Thanks anyway :)

      Delete
  2. Here is a generalized BIT range update problem:

    https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=588&page=show_problem&problem=4454

    ReplyDelete
  3. hey i don't get concept of range update. for adding v to every number in original array in range a,b, do we not have top call point update function on binary index tree for every index in range a to b,. can't we think it as point updates for every index in a to b. thus how using only two point update Update(a, v); Update(b+1, -v) does the job of all point updates in index a to b

    ReplyDelete
  4. hey i don't get concept of range update. for adding v to every number in original array in range a,b, do we not have top call point update function on binary index tree for every index in range a to b,. can't we think it as point updates for every index in a to b. thus how using only two point update Update(a, v); Update(b+1, -v) does the job of all point updates in index a to b

    ReplyDelete
  5. Very nice tutorial :)
    I have a doubt in the update(a,b,v) which adds v to all elements from index a to index b.Suppose N=8 i.e there are total 8 elements. Now update(3,6,10) will update(add 10 to) elements from index 3 to index 6. update(3,6,10) can be performed as update(3,10) and update(7,-10). update(3,10) adds 10 to indexes 3,4 and 8. Similarly update(7,-10) adds -10 to indexes 7 and 8.Now to find sum(6) which is the sum of all elements from index 1 to 6 , will be sum(5...6)+sum(1.....4) but index 5 and 6 were not updated. So I want to ask how is it giving the correct result?

    ReplyDelete
    Replies
    1. Read the top coder tutorial properly ... See the table of responsibility

      Delete
    2. Although i am 3 years late but i was also stuck in a similar situation.
      The point query won't give the sum upto 'x' but will give the given value at that idx.
      So indices 5 and 6 won't be changed but while calculating query(5) we will iterate through 5-->4.

      Delete
  6. Very nice tutorial :)
    I have a doubt in the update(a,b,v) which adds v to all elements from index a to index b.Suppose N=8 i.e there are total 8 elements. Now update(3,6,10) will update(add 10 to) elements from index 3 to index 6. update(3,6,10) can be performed as update(3,10) and update(7,-10). update(3,10) adds 10 to indexes 3,4 and 8. Similarly update(7,-10) adds -10 to indexes 7 and 8.Now to find sum(6) which is the sum of all elements from index 1 to 6 , will be sum(5...6)+sum(1.....4) but index 5 and 6 were not updated. So I want to ask how is it giving the correct result?

    ReplyDelete
  7. Great Tutorial thanks...

    ReplyDelete
  8. If we are using Range update and point query...In which We have all the updates first and then all the queries we can do it this way without writing update and query functions.
    Also we need no extra space.Lets have an array named arr.

    If Update(a,b,v) comes we simply do arr[a]+=v; and arr[b+1]-=v;

    After all updates Query(x) will come so do this..

    int sum = 0;
    for(int i = 1; i < =n; ++i)
    {
    sum += arr[i];
    arr[i] = sum;
    }


    Atlast our query is arr[i]; return it.

    If you find any bug please do comment.

    ReplyDelete
  9. Replies
    1. can you tell how to do query in 3-D BIT from (x1,y1,z1) to (x2,y2,z2) ????

      Delete
    2. for 3D bit, you gotta do a lot of inclusion and exclusion. its like set theory.

      Delete
  10. In the 2nd part (range update, point query) -
    "Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, v). Now what will happen if you call Query(x)?"

    shouldn't it be Update(b+1, -v) ?

    ReplyDelete
    Replies
    1. Updated the post, thanks for figuring that out. :) Have a nice day!

      Delete
  11. what is the meaning of the line
    "This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it"
    I read it at many places but I am not able to understand its meaning

    ReplyDelete
  12. i got it.sorry for inconvenience..i was thinking it in another way

    ReplyDelete
  13. nice tutorial you have there :D but I'm wondering if we can apply the range update and range query in BIT 2D. For example add v to rectangle (a,b) (x,y) and get the sum of a rectangle (a,b) (x,y).

    ReplyDelete
  14. Thank You :)
    Range Querry Range Update part is really nicely described

    ReplyDelete
  15. How to perform range update and range query using two dimensional bit trees?

    ReplyDelete
  16. Range update and point query can be considered like this; consider x[i] = f[i]-f[i-1] ; i>0 and f[0] = 0 where f is the original array, range update (from l to r) on f translates to point updates( at l, r+1) and cumulative sum till x[i] is f[i].

    ReplyDelete
  17. Update(b+1, -v*b) , shouldn't it be Update(b+1,-v*b + v*(a-1)) ?

    ReplyDelete
  18. update(a, v *(a - 1)) will add v*(a-1) to all cumulative sums >= a , so we don't need to add it again

    ReplyDelete
  19. This helped in understanding SPOJ-HORRIBLE sol in BIT . Thanks :)

    ReplyDelete
  20. Your blog has given me that thing which I never expect to get from all over the websites. Nice post guys!

    ReplyDelete
  21. Read so many tutorials... But this gave me super clarity... Thank you so much...

    ReplyDelete