P4514 上帝造题的七分钟——二维树状数组

P4514 上帝造题的七分钟

求的是矩阵里所有数的和；

维护四个树状数组；

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int b[maxn][maxn],bi[maxn][maxn],bj[maxn][maxn],bij[maxn][maxn];

char s[];

int n,m,num;

void add(int x,int y,int z) {for(int i=x;i<=n;i+=i&(-i)) for(int j=y;j<=m;j+=j&(-j)) b[i][j]+=z;}

void addi(int x,int y,int z) {for(int i=x;i<=n;i+=i&(-i)) for(int j=y;j<=m;j+=j&(-j)) bi[i][j]+=z;}

void addj(int x,int y,int z) {for(int i=x;i<=n;i+=i&(-i)) for(int j=y;j<=m;j+=j&(-j)) bj[i][j]+=z;}

void addij(int x,int y,int z) {for(int i=x;i<=n;i+=i&(-i)) for(int j=y;j<=m;j+=j&(-j)) bij[i][j]+=z;}

int query_(int x,int y) { int ans=; for(int i=x;i;i-=i&(-i)) for(int j=y;j;j-=j&(-j)) ans+=b[i][j]; return ans;}

int query_i(int x,int y) { int ans=; for(int i=x;i;i-=i&(-i)) for(int j=y;j;j-=j&(-j)) ans+=bi[i][j]; return ans;}

int query_j(int x,int y) { int ans=; for(int i=x;i;i-=i&(-i)) for(int j=y;j;j-=j&(-j)) ans+=bj[i][j]; return ans;}

int query_ij(int x,int y) { int ans=; for(int i=x;i;i-=i&(-i)) for(int j=y;j;j-=j&(-j)) ans+=bij[i][j]; return ans;}

void add_all(int x,int y,int num)

{

    add(x,y,num);

    addi(x,y,num*x);

    addj(x,y,num*y);

    addij(x,y,num*x*y);

}

int query(int x,int y)

{

    int ans=;

    ans+=query_(x,y)*(x*y+x+y+)-query_i(x,y)*(y+)-query_j(x,y)*(x+)+query_ij(x,y);

    return ans;

}

int main()

{

    scanf("%s%d%d",s,&n,&m);

    while(~scanf("%s",s))

    {

        int x1,y1,x2,y2;

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        if(s[]=='L')

        {

            scanf("%d",&num);

            add_all(x1,y1,num);

            add_all(x1,y2+,-num);

            add_all(x2+,y1,-num);

            add_all(x2+,y2+,num);

        }

        else

        {

            printf("%d\n",query(x2,y2)-query(x2,y1-)-query(x1-,y2)+query(x1-,y1-));

        }

    }

    return ;

}

我写的比较丑了，也可以将加入和查询操作放在结构体里面；

struct node

{

    int tree[][];

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

    void add(int x,int y,int num)

    {

        for(int i=x; i<=n; i+=lowbit(i))

            for(int j=y; j<=m; j+=lowbit(j))

                tree[i][j]+=num;

    }

    int query(int x,int y)

    {

        int res=;

        for(int i=x; i>=; i-=lowbit(i))

            for(int j=y; j>=; j-=lowbit(j))

                res+=tree[i][j];

        return res;

    }

}b,bi,bj,bij;

差分和前缀和的思想；