https://loj.ac/problem/133

题目描述

??维护一个\(n*m\)的矩阵\(A\),支持两种操作：\(①\)把\(A_{i,j}\)加上k；\(②\)询问左上角为\((a,b)\)，右下角为\((c,d)\)的矩阵中所有数的和。

思路

??二维树状数组的模板题。我们用\(p[i][j]\)表示以\((1,1)\)为左上角，\((i,j)\)为右上角的矩阵中所有数的和，那么修改操作改为二重循环即可。而对矩阵的询问操作我们可以转化为四个左上角为\((1,1)\)矩阵的差、和来求解。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<13)+10;

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(ll x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>=10)write(x/10);
    putchar((x%10)+'0');
}

ll p[N][N],n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y,int w)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            p[i][j]+=w;
}
ll query(int x,int y)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            res+=p[i][j];
    return res;
}
ll f(int a,int b,int c,int d)
{
    return query(c,d)-query(a-1,d)-query(c,b-1)+query(a-1,b-1);
}

int main() 
{
    n=read();m=read();
    int op;
    while(~scanf("%d",&op))
    {
        if(op==1)
        {
            int x=read(),y=read(),k=read();
            add(x,y,k);
        }
        else
        {
            int a=read(),b=read(),c=read(),d=read();
            write(f(a,b,c,d));
            putchar('\n');
//          printf("%lld\n",f(a,b,c,d));
        }
    }
}

打鼹鼠

原文：https://www.cnblogs.com/fangbozhen/p/11755411.html