hihocoder 1336 二维树状数组

http://hihocoder.com/problemset/problem/1336

You are given an N × N matrix. At the beginning every element is 0. Write a program supporting 2 operations:

1. Add x y value: Add value to the element Axy. (Subscripts starts from 0

2. Sum x1 y1 x2 y2: Return the sum of every element Axy for x1 ≤ x ≤ x2, y1 ≤ y ≤ y2.

Input

The first line contains 2 integers N and M, the size of the matrix and the number of operations.

Each of the following M line contains an operation.

1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000

For each Add operation: 0 ≤ x < N, 0 ≤ y < N, -1000000 ≤ value ≤ 1000000

For each Sum operation: 0 ≤ x1 ≤ x2 < N, 0 ≤ y1 ≤ y2 < N

Output

For each Sum operation output a non-negative number denoting the sum modulo 109+7.

Sample Input

5 8
Add 0 0 1
Sum 0 0 1 1
Add 1 1 1
Sum 0 0 1 1
Add 2 2 1
Add 3 3 1
Add 4 4 -1
Sum 0 0 4 4

Sample Output

1
2
3

题目大意：n*n的矩阵初始化为0，m个操作，Add a b c，表示给矩阵第a行第b列的值加上c；Sum x1 y1 x2 y2表示求这个小矩阵内所有元素之和。(矩阵下标从0开始)

思路：很明显是二维树状数组，注意下标是从0开始的，因此我们把所有坐标都+1，这样才满足树状数组的要求。说一下求和问题的转化吧，先看下图：

hihocoder 1336 二维树状数组

要求右下角蓝色的那个矩阵的元素之和，假设用sum(x,y)表示从第1行到第x行，第1列到第y列的元素之和，那么问题可以转化：

求(S1+S2+S3+S4)-(S1+S3)-(S1+S2)+S1，然后大家应该都懂了。

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=1005;
const int MOD=1e9+7;

int n,m;
int tree[maxn][maxn];
char s[10];

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

void add(int x,int y,int v)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=n;j+=lowbit(j))
			tree[i][j]=(tree[i][j]+v)%MOD;
}

int query(int x,int y)
{
	if(x==0||y==0)
		return 0;
	int sum=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			sum=(sum+tree[i][j])%MOD;
	return sum;
}

int main()
{
	scanf("%d %d",&n,&m);
	int x1,x2,y1,y2,v;
	for(int i=0;i<m;i++)
	{
		scanf("%s",s);
		if(s[0]=='A')
		{
			scanf("%d %d %d",&x1,&y1,&v);
			++x1,++y1;
			add(x1,y1,v);
		}
		else
		{
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			++x1,++x2,++y1,++y2;
			printf("%d\n",(query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1)+MOD)%MOD);
		}
	}
	return 0;
}

hihocoder 1336 二维树状数组

相关推荐