二维树状数组板子题。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 #define mem(a,b) memset(a,b,sizeof(a)) 10 #define ll long long 11 #define inf 1000000000 12 #define maxn 40000 13 #define eps 1e-12 14 #define mod 1000000007 15 #define N 3005 16 inline int read() 17 { 18 int x=0,f=1;char ch=getchar(); 19 while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} 20 while(ch>='0'&&ch<='9') {x=10*x+ch-'0';ch=getchar();} 21 return x*f; 22 } 23 int c[N][N],n; 24 int lowbit(int i) 25 { 26 return i&(-i); 27 } 28 int sum(int x,int y) 29 { 30 int ret=0; 31 for(int i=x;i>0;i-=lowbit(i)) 32 { 33 for(int j=y;j>0;j-=lowbit(j)) 34 ret+=c[i][j]; 35 } 36 return ret; 37 } 38 void add(int x,int y,int d) 39 { 40 for(int i=x;i<=n;i+=lowbit(i)) 41 for(int j=y;j<=n;j+=lowbit(j)) 42 { 43 c[i][j]+=d; 44 } 45 } 46 int main() 47 { 48 int k,op,x,y,i,j; 49 while(~scanf("%d%d",&i,&n)) 50 { 51 mem(c,0); 52 while(1) 53 { 54 op=read(); 55 if(op==3) break; 56 if(op==1) { 57 x=read();y=read();k=read(); 58 add(x+1,y+1,k); 59 } 60 else{ 61 int l,b,r,t; 62 l=read();b=read();r=read();t=read(); 63 l++;b++;r++;t++; 64 printf("%d ",sum(r,t)-sum(r,b-1)-sum(l-1,t)+sum(l-1,b-1)); 65 } 66 } 67 } 68 return 0; 69 }