hihocoder-Week 172--Matrix Sum
Matrix Sum
描述
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 y1: Return the sum of every element Axy for x1 ≤ x ≤ x2, y1 ≤ y ≤ y2.
输入
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
输出
For each Sum operation output a non-negative number denoting the sum modulo 109+7.
- 样例输入
-
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
- 样例输出
-
1 2 3
题解：
二维树状数组
假设我们有二维数组A[1..N][1..N]，二维树状数组可以支持对A[][]进行如下操作：
1. add(x, y, val): A[x][y] += val
2. sum(x, y): 求和sum(A[1..x][1..y])
和一维情况类似，能支持以上两个操作实际就能支持任意修改A[x][y]的值以及求一个子矩阵A[a..b][c..d]的和。
二维树状数组以上两个操作的复杂度都是O(logNlogN)的。
二维树状数组BIT2[x][y]与A[][]的对应关系如下图：
直观理解就是x坐标和y坐标分别是一个一维树状数组，假设一维情况中BIT[x]对应的是A[i1], A[i2] ... A[ik]， BIT[y]对应的是A[j1], A[j2], ... A[jt]。那么BIT2[x][y] 相当于笛卡尔积 {i1, i2, ... ik} x {j1, j2, ... jt}：
BIT2][x][y] = ΣA[i][j] | {i in {i1 ... ik}且 j in {j1 ... jt}}
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAXN = 1000 + 10;
const int MOD = 1e9 + 7;
int n, m, mp[MAXN][MAXN];
inline int lowbit(int x){
return ( x & (-x));
}
void Add(int x, int y, int val){
for(int i=x; i <= n; i += lowbit(i) ){
for(int j=y; j <= n; j += lowbit(j) ){
mp[i][j] += val;
mp[i][j] %= MOD;
}
}
}
long long GetSum(int x1, int y1, int x2, int y2){
long long ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
for(int i=x2; i>0; i-=lowbit(i)){
for(int j=y2; j>0; j-=lowbit(j)){
ans1 += mp[i][j];
ans1 %= MOD;
}
}
for(int i=x1; i>0; i-=lowbit(i)){
for(int j=y1; j>0; j-=lowbit(j)){
ans2 += mp[i][j];
ans2 %= MOD;
}
}
for(int i=x1; i>0; i-=lowbit(i)){
for(int j=y2; j>0; j-=lowbit(j)){
ans3 += mp[i][j];
ans3 %= MOD;
}
}
for(int i=x2; i>0; i-=lowbit(i)){
for(int j=y1; j>0; j-=lowbit(j)){
ans4 += mp[i][j];
ans4 %= MOD;
}
}
return (ans1 + ans2 - ans3 - ans4 + MOD) % MOD;
}
int main(){
freopen("in.txt", "r", stdin);
int x1, x2, y1, y2, val;
long long ans;
char ch[10];
while(scanf("%d %d", &n, &m) != EOF){
memset(mp, 0, sizeof(mp));
for(int i=0; i<m; ++i){
getchar();
scanf("%s", ch);
if(strcmp(ch, "Add") == 0){
scanf("%d %d %d", &x1, &y1, &val);
Add(x1 + 1, y1 + 1, val);
}else if(strcmp(ch, "Sum") == 0){
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
ans = GetSum(x1, y1, x2 + 1, y2 + 1);
printf("%lld
", ans );
}
}
}
return 0;
}