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.

SPOJ RPAR : Raining Parabolas

6906. Raining Parabolas

Problem Summery

Given an array of n items h_i ( 0≤i<n ), we have to perform an update operation for a given range [i,j] such that, h_x = (h_x + f(x))%M, ( i≤x≤j and f(x) = ax²+bx+c ). We also have to perform a query operation for a range [i,j] such that, result = (h_i + h_i+1 + h_i+2 + … + h_j)%M.

Solution Idea

Solution idea with the help of a segment tree is quite simple. First, we need to observe the types of information we need to store on each node of the tree. As we will be facing range updates, lazy propagation can be utilized, so, we can have three carry variables, namely ca, cb, cc. If we look closely to the update procedure, parts with x² are added together and parts with x are added together and there is another part which are the constants. We can resemble them namely with variables, a, b, c, i.e. a is the variable that holds the sum for x² part, b is the variable that holds the sum for x part and c is the last one that holds the constant part. Also, we can keep the pre-computed values of sum of x² and x on tree node ranges for the ease of calculation.

Now, let’s dissect the update part. Say, on node p (i to j) we already have in a:

a₁x_i² + a₂x_i+1² + a₃x_i+2² + … + a_nx_j²

Now we want to add a new parabola (a, b, c) on this range, as only x² parts will be added here, so the new value of a on this node will be:

(a₁+a)x_i² + (a₂+a)x_i+1² + (a₃+a)x_i+2² + … + (a_n+a)x_j²

So, we can easily see the extra value added with the previous in variable a:

a * (sum of x² in range [i,j])

Similarly, for x part, i.e. variable b we can show the added value is:

b * (sum of x in range [i,j])

And for the constant part, i.e. variable c we can show the added value is:

c * n where n is the size of range [i,j];

So we can perform these updates now using lazy propagation, and query is also done in the similar way, the final result for a range is simply the sum of variable a, b, c from that range. And obviously modulus operations must be handled properly.

Have fun!

Binary Tree -- N Nodes & H Height

The problem:

You are told that you have N unique numbers, how many different binary trees are possible with those N numbers (i.e. nodes) which has exactly H height.

Analysis:

If we look closely, it will be not that hard to figure out that, the problem actually wants to know, how many different binary trees are possible to build with N nodes, each of which has exactly H height allowing rotations. Here, two trees are different when their structures are different. For example:

           @                   @
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

Solution:

I don't know whether this problem has a mathematical solution or not, I have searched for it and found nothing... But, if the values N and H supports, this problem can be solved with a dynamic programming approach.

When we want to build a tree with N nodes and H height, we can select a node as a root, so, we can put 1 to N-2 nodes on the left subtree of height H-1 or less and N-2 to 1 nodes on the right subtree of height H-1 or less, satisfying that, at least one of the subtree has a height H-1. So, by using proper base condition, we can find the number of different trees of exactly H height from this recursive formulation, and we can express the relation as follows,

if k == 1 then exactTrees( N, D ) = ( n == 1 )
if n <= 1 then exactTrees( N, D ) = 0
for all {L, R} such that L, R > 0 and L + R = N - 1:
exactTrees( N, D ) += exactTrees( L, D - 1 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += smallerTrees( L, D - 2 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += exactTrees( L, D - 1 ) * smallerTrees( R, D - 2 )

This is pretty obvious, because, if we want to get a tree of height H from any node, either one or both of its subtrees must have a height H - 1, and if we have N nodes at any step, we need to take 1 node as root, and then if we take i nodes for left subtree, we have N - 1 - i nodes left for the right subtree.
When we calculate exact height, we need to consider that a subtree may have a smaller height, so we need to calculate smallerTrees( N, D ) separately, but actually it is a bit easier:

if n < 0 or k <= 0 then smallerTrees( N, D ) = 0
if k == 1 then smallerTrees( N, D ) = ( n == 1 )
if n <= 1 then smallerTrees( N, D ) = 1
else
for all {L, R} such that L, R > 0 and L + R = N - 1:
smallerTrees( N, D ) += smallerTrees( L, D - 1 ) * smallerTrees( R, D - 1 )

Sample program:

First one goes the recursive algorithm (with dp):

// states: nodes, height
int exact[202][101], smaller[202][101];

int smallTrees(int n, int k)
{
    if(n<0 || k<=0) return 0;
    if(k==1) return n==1;
    if(n<=1) return 1;
 
    int &ret = smaller[n][k], l, r;
    if(ret!=-1) return ret;
 
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += smallTrees(l, k-1)*smallTrees(r, k-1);
        }
    }
    return ret;
}

int exactTrees(int n, int k)
{
    if(k==1) return n==1;
    if(n<=1) return 0;

    int &ret = exact[n][k], l, r;
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += exactTrees(l, k-1)*exactTrees(r, k-1);
            ret += exactTrees(l, k-1)*smallTrees(r, k-2);
            ret += smallTrees(l, k-2)*exactTrees(r, k-1);
        }
    }
    return ret;
}

Here is the iterative version (a little complex):

// states: height, nodes
int exactTrees[101][202], smallTrees[101][202];

void solve(int n, int k)
{
    int d, i, j;
    exactTrees[1][1] = 1;
    for(d=2; d<=k; d++) // depth
    {
        for(i=1; i<=n; i+=2) // number of nodes
        {
            for(j=1; j<=i-1; j+=2) // left & right
            {
                exactTrees[d][i] += exactTrees[d-1][j]*exactTrees[d-1][i-1-j];
                exactTrees[d][i] += exactTrees[d-1][j]*smallTrees[d-2][i-1-j];
                exactTrees[d][i] += smallTrees[d-2][j]*exactTrees[d-1][i-1-j];
            }
        }
        for(i=1; i<=n; i+=2) // update smaller tree
        {
            smallTrees[d-1][i] += smallTrees[d-2][i]+exactTrees[d-1][i];
        }
    }
}

[P.S. The result of this problem grows very rapidly along with the increase of N and H, so, it may easily run out of range, normally problems like this requires the result with respect to some modulus values.]

Similar problem:

USACO Section: 2.3, Problem: Cow Pedigrees, Code: nocows.
[P.S. Links won't work for usaco, you need to reach level 2.3 if you want to see the problem yourself.]
If you find any more problem regarding this, please post it as a comment below.