Can anybody help me understand the solution of this problem using segment tree?

I have been learning 2-D BIT lately.

But I am having difficulty implementing range updates in it.

Eg. Suppose we have a matrix M[][].There are 2 types of queries:

1.ADD x1 y1 x2 y2 val

This adds val to all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

2.SUM x1 y1 x2 y2

This query returns the sum of all matrix elements which have their x-coordinate between x1 and x2 and y-coordinate between y1 and y2.

I am having trouble implementing the first query using 2-D BIT.

Had point(x1, y1) and point(x2, y2) been same, following code would work :

void update(int x1, int y1, ll val)

{

int x, y;

x=x1;

while(x<=n){

    y=y1;

    while(y<=m){                  //Update y coordinate

       ft[x][y]+=val;        //ft stores BIT

       y+=(y&-y);

    }

    x+=(x&-x);

}

return;

}

How to go about it if I have to update the whole range?

So, I was trying to solve this problem on a codechef contest that ended just now.I tried to reduce the expression of g(n).The maximum I could simplify is upto this point:

g(n) = pow(4, n) + 2*(pow(4,n)-1)/3 + Summation of (pow(4,n-k)*f(k)) where k ranges from n to 1.

But I couldn't find a way to find sum of function f upto a point.

On looking at accepted codes, I find that this question was to be done using Matrix Multiplication, kind of what we do in finding fibonacci numbers.

I want to know how do you guess the values in the matrix to be multiplied.?Is there a particular way to be followed around such questions..?