這題是一個簡單的二維數(shù)組操作題，簡單是因為，這個和你在網(wǎng)上找到的介紹一維樹狀數(shù)組的操作差不多，只不過這個是二維的而已。
對于一個二維的樹狀數(shù)組，你可以這樣認(rèn)為:是一個一維數(shù)組，但是每個元素又是一個一維數(shù)組，也就是一維數(shù)組套一維數(shù)組。
那么更新時，可以認(rèn)為是更新每個一維數(shù)組的值，但是一維數(shù)組又是一個一維數(shù)組，那么還得更改里面的一維數(shù)組的值。
那么update函數(shù)就變成了下面的代碼:
update
1
void update(int x,int y,int val)
2
{
3
int y1;
4 while(x < max_x)
5
{//更改外面的一維數(shù)組
6 y1 = y;
7 while(y1 <= max_y)
8 {//對每個外面的一維數(shù)組所包含的一維數(shù)組進行更改
9 tree[x][y1] += val;
10 y1 += (y1 & -y1);
11
}
12 x += (x & -x);
13
14 }
15
}
同樣的求和函數(shù)read()就會變成如下代碼:
read
1int read(int x,int y)
2{
3int y1,ret;
4while(x > 0)
5 {//求外面的一維數(shù)組的和
6 y1 = y;
7 while(y1 > 0)
8 {//對每個一維數(shù)組所包含的一維數(shù)組求和
9 ret += tree[x][y1];
10 y1 -= (y1 & -y1);
11 }
12 x -= (x & -x);
13 }
14return ret;//最后的結(jié)果
15}
16
對于這兩個函數(shù)理解了之后，這題就是一個很簡單的題了，update函數(shù)不用變，但是求和時就要改變了，不過也不能叫改變，因為，求和時會用到上面的read函數(shù)。但是所要求是一個矩形，也就是不一定是從(1,1)開始。那么我們可以變成四個矩形的和或者差,比如我們要求sum(x1,y1,x2,y2)時我們可以變成
read(r,t)-read(l-1,t)-read(r,b-1)+read(l-1,b-1)。也就是大矩形減去兩個小矩形然后再加一個多減去的矩形。