二维树状数组
注意求区间和 要分成多个部分来加减
还有就是 注意0的情况
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 1100; int c[MAXN + 10][MAXN + 10],a[MAXN + 10][MAXN + 10]; int n,m; int Lowbit(int x){ return x &(-x); } void Add(int x,int y,int d){ for(int i = x;i <= MAXN;i += Lowbit(i)){ for(int j = y;j <= MAXN ;j += Lowbit(j)){ c[i][j] += d; } } } int Sum(int x,int y){ int ret = 0; for(int i = x;i > 0;i -= Lowbit(i)){ for(int j = y;j > 0;j -= Lowbit(j)){ ret += c[i][j]; } } return ret; } int main(){ while(~scanf("%d%d",&n,&m)){ memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); while(1){ int flag; scanf("%d",&flag); if(flag == 3) break; if(flag == 1){ int x,y,c1; scanf("%d%d%d",&x,&y,&c1); a[x + 2][y + 2] += c1; Add(x+2,y+2,c1); } else{ int l,b,r,t; scanf("%d%d%d%d",&l,&b,&r,&t); printf("%d\n",Sum(r + 2,t + 2) - Sum(l + 1,t +2) - Sum(r + 2,b + 1) + Sum(l + 1,b + 1)); } } } return 0; }