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?