hihoCoder Week 172 Matrix Sum (二维树状数组)

xiaoxiao2021-02-28  31

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB

描述

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.

输入

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 二维树状数组讲解: http://blog.csdn.net/z309241990/article/details/9615259 http://blog.csdn.net/int64ago/article/details/7429868 简单的二维树状数组求区间面积: Sum([x1,x2],[y1,y2])=query(x2,y2)+query(x1-1,y1-1)-query(x2,y1-1)-query(x1-1,y2); 这道题的取模有点坑:负数取模 #include<cstdio> #include<cstring> typedef long long ll; const int MAXN = 2000+10; #define MOD 1000000007 ll c[MAXN][MAXN]; int n; int lowbit(int x) { return x&(-x); } void update(int x,int y,ll value) { for(int i=x;i<=n;i+=lowbit(i)) { for(int j=y;j<=n;j+=lowbit(j)) { c[i][j]=c[i][j]+value; } } } ll query(int x,int y) { ll sum=0; for(int i=x;i>0;i-=lowbit(i)) { for(int j=y;j>0;j-=lowbit(j)) { sum=sum+c[i][j]; } } return sum%MOD; } int main() { int m; scanf("%d%d",&n,&m); memset(c,0,sizeof(c)); char str[5]; while(m--) { getchar(); scanf("%s",str); if(str[0]=='A') { int x,y,value; scanf("%d%d%d",&x,&y,&value); x++;y++; update(x,y,value); } else { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++;y1++; x2++;y2++; ll ans=query(x2,y2)+query(x1-1,y1-1)-query(x2,y1-1)-query(x1-1,y2); printf("%lld\n",(ans+MOD)%MOD); } } }
转载请注明原文地址: https://www.6miu.com/read-1600060.html

最新回复(0)