这是一道模板题。
给出一个 n×mn×m 的零矩阵 AA，你需要完成如下操作：
1 x y k：表示元素 Ax,yAx,y 自增 kk；2 a b c d：表示询问左上角为 (a,b)(a,b)，右下角为 (c,d)(c,d) 的子矩阵内所有数的和。Input
输入的第一行有两个正整数 n,mn,m；
接下来若干行，每行一个操作，直到文件结束。
Output
对于每个 2 操作，输出一个整数，表示对于这个操作的回答。
Example
2 2
1 1 1 3
1 2 2 4
2 1 1 2 27Hint
对于 10%10% 的数据，n=1n=1；
对于另 10%10% 的数据，m=1m=1；
对于全部数据，1≤n,m≤212,1≤x,a,c≤n,1≤y,b,d≤m,|k|≤1051≤n,m≤212,1≤x,a,c≤n,1≤y,b,d≤m,|k|≤105，保证操作数目不超过 3×1053×105，且询问的子矩阵存在。
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m; ll a[5010][5010]; ll lowbit(ll x){ return (x&-x); } void add(ll x,ll y,ll k){ for(ll i=x;i<=n;i+=lowbit(i)){ for(ll j=y;j<=m;j+=lowbit(j)){ a[i][j]+=k; } } } ll getsum(ll x,ll y){ ll sum=0; for(ll i=x;i>0;i-=lowbit(i)){ for(ll j=y;j>0;j-=lowbit(j)){ sum+=a[i][j]; } } return sum; } int main(){ scanf("%lld%lld",&n,&m); ll type; while(scanf("%lld",&type)!=EOF){ if(type==1){ ll x,y,k; scanf("%lld%lld%lld",&x,&y,&k); add(x,y,k); } if(type==2){ ll x1,y1,x2,y2; scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); printf("%lld\n",getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1)); } } return 0; }
二维树状数组 1：单点修改，区间查询 LibreOJ - 133
原文：https://www.cnblogs.com/xxxsans/p/12747620.html