题目链接 : http://poj.org/problem?id=1195
#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<map> using namespace std; int num[1050][1050],s; int lowbit(int x) { return x&(-x); } void add(int x,int y,int val) { for(int i=x; i<=s; i+=lowbit(i)) for(int j=y; j<=s; j+=lowbit(j)) num[i][j]+=val; } int query(int x,int y) { int ans=0; for(int i=x; i>0; i-=lowbit(i)) for(int j=y; j>0; j-=lowbit(j)) ans+=num[i][j]; return ans; } int main() { int t,q,x,y,l,r,a; scanf("%d%d",&t,&s); memset(num,0,sizeof(num)); while(scanf("%d",&q),q<3) { if(q==1) { scanf("%d%d%d",&x,&y,&a); x++, y++; add(x,y,a); } else if(q==2) { scanf("%d%d%d%d",&x,&y,&l,&r); x++,y++,l++,r++; printf("%d\n",query(l,r)-query(l,y-1)-query(x-1,r)+query(x-1,y-1)); } } return 0; }