树状数组

参考：https://hihocoder.com/discuss/question/4956

注意树状数组下标从1开始，所以在主函数运用的时候注意下标的改动

二维树状数组的运用：

hiho1336 矩阵 matrix sum

#include <iostream>
#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long LL;

const int maxn=1000+5,
          mod=1e9+7;

LL BIT[maxn][maxn];
int N,m;

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

void add(int x,int y,int val)
{
    for(int i=x;i<maxn;i+=lowbit(i))
    {
        for(int j=y;j<maxn;j+=lowbit(j))
        {
            BIT[i][j]=(BIT[i][j]+val)%mod;
        }
    }
}

int sum(int x,int y)
{
    LL ret=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ret=(ret+BIT[i][j])%mod;
        }
    }
    return (int)ret;
}

int main()
{
    mem(BIT,0);
    scanf("%d%d",&N,&m);
    char op[10];
    for(int i=0;i<m;i++)
    {
        scanf("%s",op);
        if(op[0]=='A')
        {
            int x,y,val;
            scanf("%d%d%d",&x,&y,&val);
            x++,y++;
            add(x,y,val);
        }
        else
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++,x2++,y1++,y2++;
            int res=(sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)+mod)%mod;
            printf("%d
",res);
        }
    }
    return 0;
}