hihocode 1336 Matrix Sum 【二维树状数组】

题目

两个操作：

 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.

注意取模，因为value可能为负值

        ans%=Mod;
       if(ans<0) ans+=Mod;

#include <iostream>
#include <cstdio>

using namespace std;
const int Max = 1010;
const int Mod = 1e9+7;
typedef long long LL;
int n;
int c[1010][1010];

int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int y,int val)
{
    for(int i=x;i<=Max;i+=lowbit(i))
    {
        for(int j=y;j<=Max;j+=lowbit(j))
        {
            c[i][j]+=val;
        }
    }
}
LL sum(int x,int y)
{
    LL res = 0;
   for(int i=x;i>0;i-=lowbit(i))
    for(int j=y;j>0;j-=lowbit(j))
        res += c[i][j];
   return res;
}
int main()
{
    int op,x,y,X,Y,val;
    string str;
    scanf("%d%d",&n,&op);
    while(op--)
    {
        cin>>str;
        if(str[0]=='A'){
            scanf("%d%d%d",&x,&y,&val);
            x++,y++;
            update(x,y,val);
        }else{//sum
            scanf("%d%d%d%d",&x,&y,&X,&Y);
            x++,y++,X++,Y++;

            LL ans =sum(X,Y)+sum(x-1,y-1)-sum(X,y-1)-sum(x-1,Y);
            ans%=Mod;
            if(ans<0) ans+=Mod;
            printf("%d
",ans);
        }
    }
    return 0;
}