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