簡單的二維樹狀數(shù)組，求一個矩形區(qū)域內的和，因為要隨時增減，而且可能減的數(shù)比原來都大，所以需要保留原來的數(shù)組。
在求矩形區(qū)域和的時候，只要用最大的矩形減去兩個小的，再加上那個多減的最小的，就OK了。1y~~
Code：
1 #include<iostream>
2 #define M 1300
3 int c[M][M],a[M][M],n;
4 int lowbit(int t){
5 return t&(t^(t-1));
6 }
7 int sum(int p,int q){
8 int x=p,y,total=0;
9 while(x>0){
10 y=q;
11 while(y>0){
12 total+=c[x][y];
13 y-=lowbit(y);
14 }
15 x-=lowbit(x);
16 }
17 return total;
18 }
19 void modify(int p,int q,int key){
20 int x=p,y;
21 while(x<=n){
22 y=q;
23 while(y<=n){
24 c[x][y]+=key;
25 y+=lowbit(y);
26 }
27 x+=lowbit(x);
28 }
29 }
30 int main()
31 {
32 int i,j,k,jj,kk,m,order,ans;
33 scanf("%d%d",&i,&n);
34 memset(c,0,sizeof(c));
35 memset(a,0,sizeof(a));
36 while(scanf("%d",&order)!=EOF){
37 if(order==3) break;
38 else if(order==1){
39 scanf("%d%d%d",&j,&k,&m);
40 ++j; ++k;
41 if(m<0&&m*(-1)>a[j][k]){
42 m=(-1)*a[j][k];
43 modify(j,k,m);
44 a[j][k]=0;
45 }
46 else{
47 modify(j,k,m);
48 a[j][k]+=m;
49 }
50 }
51 else if(order==2){
52 scanf("%d%d%d%d",&j,&jj,&k,&kk);
53 ++j; ++jj; ++k; ++kk;
54 //printf("%d ",sum(n,n));
55 ans=sum(k,kk)+sum(j-1,jj-1)-sum(k,jj-1)-sum(j-1,kk);
56 printf("%d\n",ans);
57 }
58 }
59 }