（未完待续）

题目链接：Vijos P1512/LibreOJ 10118/LibreOJ 133/信息学奥赛一本通 T1540。

题目

题目描述

这是一道模板题。
给出一个 $n\times m$ 的零矩阵 $A$，你需要完成如下操作：

• $\texttt{1 x y k}$：表示元素 $A _ {x,y}$ 自增 $k$；
• $\texttt{2 a b c d}$：表示询问左上角为 $(a,b)$，右下角为 $(c,d)$ 的子矩阵内所有数的和。

数据范围

对于全部数据，$1\leq n,m\leq 2^{12},1\leq x,a,c\leq n,1\leq y,b,d\leq m,|k|\leq 10^5$，保证操作数目不超过 $3\times 10^5$，且询问的子矩阵存在。

题解

思路

这是二维树状数组的模板题，照做就行。

代码

代码也没什么好说的，写模板就可以了。

#include<cstdio>
typedef long long ll;
//以上为头文件
const int MAXN=(1<<12)+5;
const int MAXM=(1<<12)+5;
struct TreeArray_2{//二维树状数组模板
    #define lowbit(x) ( (x) & ( - (x) ) ) //宏定义lowbit(x)
    int n,m;//树状数组的行和列
    ll unit[MAXN][MAXM];//储存数据的数组
    void Update(int x,int y,ll val){//更新函数
        register int i,j;
        i=x;
        while(i<=n){
            j=y;
            while(j<=m){
                unit[i][j]+=val;
                j+=lowbit(j);
            }
            i+=lowbit(i);
        }
        return;
    }
    ll Query(int x,int y){//查询函数
        register int i,j;
        register ll sum=0;
        i=x;
        while(i){
            j=y;
            while(j){
                sum+=unit[i][j];
                j-=lowbit(j);
            }
            i-=lowbit(i);
        }
        return sum;
    }
    #undef lowbit //取消对lowbit(x)的宏定义
};
int n,m,opt;
TreeArray_2 T;
int main(void){
    scanf("%d%d",&n,&m);
    T.n=n,T.m=m;//确定树状数组大小
    while(scanf("%d",&opt)!=EOF){//多次操作，直到文件末尾
        if(opt==1){
            static int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            T.Update(x,y,k);
        }
        if(opt==2){
            static int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            printf("%lld\n",T.Query(c,d)-T.Query(a-1,d)-T.Query(c,b-1)+T.Query(a-1,b-1));//注意细节
        }
    }
    return 0;
}