poj 1195

题意：这道题目只是题意自己就去理解了半天，大概题意如下：给出i一个n*n的矩阵，初始化为均为0，还有关于这个矩阵的几种操作，操作如下：命令1：(X Y A)对位于坐标（X Y）的值加A；命令2：（L B R T）求出位于L<=x<=R，B<=y<=T的值的和；命令3：退出不做任何操作。

 

思路分析如下：二维树状数组，典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和，注意一下就可以了:sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);

 

 

代码如下：

 

#include<iostream>
using namespace std;
const int Max = 1030;

int row, col, ar[Max][Max];

int lowbit(int x)
{
    return x & (-x);
}

void add(int i, int j, int w)
{
    int tmpj;
    while(i <= row)
	{
        tmpj = j;
        while(tmpj <= col)
		{
            ar[i][tmpj] += w;
            tmpj += lowbit(tmpj);
        }
        i += lowbit(i);
    }
}

int sum(int i, int j)
{
    int tmpj, ans = 0;
    while(i > 0)
	{
        tmpj = j;
        while(tmpj > 0)
		{
            ans += ar[i][tmpj];
            tmpj -= lowbit(tmpj);
        }
        i -= lowbit(i);
    }
    return ans;
}

int main()
{
    int n, ord, x, y, xx, yy, w;
    while(scanf("%d%d", &ord, &n) != EOF)
	{
        memset(ar, 0, sizeof(ar));
        row = col = n;
        while(scanf("%d", &ord) && ord != 3)
		{
            if(ord == 1)
			{
                scanf("%d%d%d", &x, &y, &w);
                x++, y++;    //  二维的其实下标为[1][1]，这个要记得。
                add(x, y, w);
            }
			else
			{
                scanf("%d%d%d%d", &x, &y, &xx, &yy);
                x ++, y ++, xx ++, yy ++;
                int ans = sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}