题面

题目链接

这是一道模板题。

给出一个  的零矩阵 ，你需要完成如下操作：

• 1 x y k：表示元素  自增 ；
• 2 a b c d：表示询问左上角为 ，右下角为  的子矩阵内所有数的和。

思路

一维树状数组的扩展

我们知道，一维树状数组可以求一段区间的和，将其扩展到二维，对于一个矩阵，每一层可以看做一个数，实际上是树状数组，每次求到每一层时求出这一层的区间和即可。也就是两个一维树状数组套一套。

容斥思想

通过和树状数组一样的思路可以求出原点到目标点的子矩阵的和，和二维前缀和相同，利用容斥思想就可以求出任意子矩阵的和。具体如图，右下角浅色子矩阵的面积可以通过面积相减得到。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,s[5000][5000];
int lowbit(int x){
    return -x&x;
}
void updata(int x,int y,int z){
	for (int i=x;i<=n;i+=lowbit(i)){
		for (int j=y;j<=m;j+=lowbit(j)){
			s[i][j]+=z;
		}
	}
}
long long getsum(int x,int y){
	long long res=0;
	for (int i=x;i>0;i-=lowbit(i)){
		for (int j=y;j>0;j-=lowbit(j)){
			res+=s[i][j];
		}
	}
	return res;
}
int main(){
	cin>>n>>m;
    int x,a,b,c,d;
    while(cin>>x){
        if(x==1){
        	cin>>a>>b>>c;
            updata(a,b,c);
        }else{
        	cin>>a>>b>>c>>d;
            cout<<getsum(c,d)-getsum(a-1,d)-getsum(c,b-1)+getsum(a-1,b-1)<<endl;
        }
    }
}