NO IMAGE

       由於英語極差,看了半天也沒看懂題目,最後參考了其他人的題解才搞懂題目,我就直接把題意貼過來了 

     

題意:這道題目只是題意自己就去理解了半天,大概題意如下:給出i一個n*n的矩陣,初始化為均為0,還有關於這個矩陣的幾種操作,操作如下:命令1:(X Y A)對位於座標(X Y)的值加A;命令2:(L B R T)求出位於L<=x<=R,B<=y<=T的值的和;命令3:退出不做任何操作。

 

思路分析如下:二維樹狀陣列,典型的動態操作題目。查詢子矩陣(x,y,xx,yy)的元素和,注意一下就可以了:sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1) sum(x-1,y-1);

      這是我做的第一道二維樹狀樹組的題目,感覺和一維的差不多,下面是題解。

 

//poj 1195
#include <stdio.h>
#include <string.h>
const int maxn = 1030;
int n, a[maxn][maxn];
int lowbit(int x)
{
return x & (-x);
}
void update(int i, int j, int v)
{
int t;
while(i <= n)
{
t = j;                        //不能改變j的值,因為每次迴圈都要用到
while (t <= n)
{
a[i][t]  = v;
t  = lowbit(t);
}
i  = lowbit(i);
}
}
int getsum(int i, int j)
{
int sum = 0, t;
while (i > 0)
{
t = j;                          //不能改變j的值,因為每次迴圈都要用到
while (t > 0)
{
sum  = a[i][t];
t -= lowbit(t);
}
i -= lowbit(i);
}
return sum;
}
int main()
{
int op, x, y, v, xx, yy;
while (scanf("%d%d",&op,&n) != EOF)
{
memset(a, 0, sizeof(a));
while (scanf("%d",&op) && op != 3)
{
if (op == 1)
{
scanf("%d%d%d",&x, &y, &v);
x  ; y  ;                         //樹狀陣列座標是從1開始的,以此要加1
update(x, y, v);
}
else
{
scanf("%d%d%d%d", &x, &y, &xx, &yy);
x   , y   , xx   , yy   ;
int ans = getsum(xx, yy) - getsum(x-1, yy) - getsum(xx, y-1)   getsum(x-1, y-1);
// 每次getsum(i, j); 得到的結果是(i,j)前面所有數的和 
printf("%d\n", ans);
}
}
}
return 0;
}