hdu - 1892 - See you~（二维树状数组（单点修改））

题意：由格子组成的一个房间，开始时每个格子都有1本书，然后来一Q个query，进行增、删、移动、查询矩形(x1, y1) - (x2, y2)内的书本数。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1892

——>>做的第一道二维树状数组题，写法基本和一维树状数组是一样的。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 1000 + 10;
int C[maxn][maxn], a[maxn][maxn];int lowerbit(int x)
{return x&(-x);
}
int sum(int x, int y)       //BIT求和
{int ret = 0;for(int i = x; i > 0; i -= lowerbit(i))for(int j = y; j > 0; j -= lowerbit(j))ret += C[i][j];return ret;
}
void add(int x, int y, int n)       //BIT加法
{for(int i = x; i < maxn; i += lowerbit(i))for(int j = y; j < maxn; j += lowerbit(j))C[i][j] += n;
}
void del(int x, int y, int n)       //BIT减法
{add(x, y, -n);
}
void mov(int x1, int y1, int x2, int y2, int n)     //BIT移动
{add(x1, y1, -n);add(x2, y2, n);
}
int main()
{int T, Q, x1, y1, x2, y2, n1, cnt = 1;char c;scanf("%d", &T);while(T--){scanf("%d", &Q);printf("Case %d:\n", cnt++);for(int i = 1; i < maxn; i++)for(int j = 1; j < maxn; j++){a[i][j] = 1;C[i][j] = lowerbit(i)*lowerbit(j);      //初始化C}while(Q--){scanf("\n%c", &c);switch(c){case 'A':{scanf("%d%d%d", &x1, &y1, &n1);x1++;y1++;add(x1, y1, n1);a[x1][y1] += n1;break;}case 'D':{scanf("%d%d%d", &x1, &y1, &n1);x1++;y1++;if(a[x1][y1] >= n1){del(x1, y1, n1);a[x1][y1] -= n1;}else{del(x1, y1, a[x1][y1]);a[x1][y1] = 0;}break;}case 'M':{scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n1);x1++;y1++;x2++;y2++;if(a[x1][y1] >= n1){mov(x1, y1, x2, y2, n1);a[x1][y1] -= n1;a[x2][y2] += n1;}else{mov(x1, y1, x2, y2, a[x1][y1]);a[x2][y2] += a[x1][y1];a[x1][y1] = 0;}break;}case 'S':{scanf("%d%d%d%d", &x1, &y1, &x2, &y2);x1++;y1++;x2++;y2++;if(x1 > x2) swap(x1, x2);if(y1 > y2) swap(y1, y2);printf("%d\n", sum(x2, y2)-sum(x2, y1-1)-sum(x1-1, y2)+sum(x1-1, y1-1));break;}}}}return 0;
}

对于add和sum

如果这样写：直接用参数x和y来做循环变量：

void add(int x, int y, int n)       //BIT加法
{for(; x < maxn; x += lowerbit(x))for(; y < maxn; y += lowerbit(y))C[x][y] += n;
}