http://poj.org/problem?id=1195
题意:有一个s*s的方格,有两种操作,给某个方格a[x][y] 加上一个数add 和 询问某一个子矩阵内所有数字的和。
思路:二维树状数组的模板。。要注意的是题目中的下标从0开始而树状数组的下标从1开始,所以下标均向右移一位。
#include <stdio.h> #include <string.h> const int maxn = 1030; int Lowbit(int x) { return x&(-x); } int c[maxn][maxn]; int n; //给a[i][j]节点加上add; void update(int i, int j, int add) { while(i <= n) { int tmp = j; while(tmp <= n) { c[i][tmp] += add; tmp += Lowbit(tmp); } i += Lowbit(i); } } //a[1][1]~a[i][j]的和(原数组) int sum(int i, int j) { int s = 0; while(i > 0) { int tmp = j; while(tmp > 0) { s += c[i][tmp]; tmp -= Lowbit(tmp); } i -= Lowbit(i); } return s; } int main() { int f; int x,y,add; int l,r,b,t; memset(c,0,sizeof(c)); while(1) { scanf("%d",&f); if(f == 0) scanf("%d",&n); else if(f == 1) { scanf("%d %d %d",&x,&y,&add); update(x+1,y+1,add); } else if(f == 2) { scanf("%d %d %d %d",&l,&b,&r,&t); l++;//均向后移一位,相对位置不变 r++; b++; t++; int ans = sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1); printf("%d\n",ans); } else if(f == 3) break; } return 0; }