二维树状数组 请教
http://acm.hdu.edu.cn/showproblem.php?pid=1892 题目地址
//二维树状数组
//
#include <stdio.h>
const int size = 1002;
int C[size][size];
int D[size][size];//数据
int lowbit(int n)
{
return n&(-n);
}
void Modify(int x, int y, int delta)
{
for(int i = x; i <= 1001; i += lowbit(i))
for(int j = y; j <= 1001; j += lowbit(j))
{
C[i][j] += delta;
}
}
int Sum(int i, int j)
{
//if(i <=0 || j <=0) return 0;
int result = 0;
for(int x = i; x > 0; x -= lowbit(x))
{
for(int y = j; y > 0; y -= lowbit(y))
{
result += C[x][y];
}
}
return result;
}
int min(int x,int y)
{
return x <y?x:y;
}
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int cas,q,ca;
char str;
int x1,y1,x2,y2,n1;
int xmin,ymin,xmax,ymax;
int ans;
scanf("%d",&cas);
for(ca = 1;ca <=cas;ca++)
{
printf("Case %d:\n",ca);
//初始化
for (x1 = 1;x1 <= 1001;x1++)
for (y1 = 1;y1 <= 1001;y1++)
{
D[x1][y1] = 1;
C[x1][y1] = lowbit(x1) * lowbit(y1); //为什么 是这样初试话 二维树状数组
}
scanf("%d",&q);
while (q--)
{
getchar();
scanf("%c",&str);
if(str == 'S') //sum
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;y1++;x2++;y2++;
xmax = max(x1,x2);
ymax = max(y1,y2);
xmin = min(x1,x2);
ymin = min(y1,y2);
int temp = Sum(xmax,ymin-1) + Sum(xmin-1,ymax) - Sum(xmin-1,ymin-1);
ans = Sum(xmax,ymax) - temp; //这样可以防止某些越界
printf("%d\n",ans);
}
else if (str == 'A') //add
{
scanf("%d %d %d",&x1,&y1,&n1);
x1++;y1++;
Modify(x1,y1,n1);
D[x1][y1] += n1;
}
else if (str == 'D') //delete
{
scanf("%d %d %d",&x1,&y1,&n1);
x1++;y1++;
if(D[x1][y1] < n1) n1 = D[x1][y1];
Modify(x1,y1,-n1);
D[x1][y1] -= n1;
}
else if (str == 'M') //move
{
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&n1);
x1++;y1++;x2++;y2++;
if (n1 > D[x1][y1])
n1 = D[x1][y1];
D[x1][y1] -= n1;
D[x2][y2] += n1;
Modify(x1,y1,-n1);
Modify(x2,y2,n1);
}
}
}
return 0;
}
/*
100
3
S 1 1 1 1
A 1 1 2
S 1 1 1 1
3
S 1 1 1 1
A 1 1 2
S 1 1 1 2
*/
