3 4 裸的二维树状数组。 所求区域和 sum = sum(R, T) – sum(R,B-1) – sum(L-1,T) + sum(L-1,B-1) 注意S及 坐标 应从1开始,所以应对输入坐标做 +1处理。 #include <cstdio> #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define S 1030 int c[S][S]; int n; int lowbit(int x) { return x&(-x); } void Updata(int x,int y,int val) { for(int i=x; i<=n; i+=lowbit(i)) { for(int j=y; j<=n; j+=lowbit(j)) { c[i][j]+=val; } } } int Getsum(int x,int y) { int sum=0; for(int i=x; i>0; i-=lowbit(i)) { for(int j=y; j>0; j-=lowbit(j)) { sum+=c[i][j]; } } return sum; } int main() { int tt, cmd, x, y, val; int x1, y1, x2, y2; freopen("B.in","r",stdin); freopen("X.out","w",stdout); scanf("%d%d",&tt,&n); memset(c,0,sizeof(c)); while(scanf("%d",&cmd) && cmd<3) { if(cmd==1) { scanf("%d%d%d",&x,&y,&val); x++; y++; Updata(x,y,val); } else if(cmd==2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++, y1++, x2++, y2++; int ans=Getsum(x2,y2)-Getsum(x2,y1-1)-Getsum(x1-1,y2)+Getsum(x1-1,y1-1); printf("%d\n",ans); } } return 0; } |