二维树状数组

复杂度
$$Q\ast log(N)\ast log(M)$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=2050,M=10010;
#define int long long 
int t1[N][N],t2[N][N],t3[N][N],t4[N][N];
int n,m;
int lowbit(int x)
{
   
	return x&-x;
}
void add(int x,int y,int d)
{
   
	for(int i=x;i<=n;i+=lowbit(i))
	{
   
		for(int j=y;j<=m;j+=lowbit(j))
		t1[i][j]+=d,t2[i][j]+=x*d,t3[i][j]+=y*d,t4[i][j]+=x*y*d;
	}
 } 
int qr(int x,int y)
{
   
	int res=0;
	for(int i=x;i;i-=lowbit(i))
	{
   
		for(int j=y;j;j-=lowbit(j))
		res+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];
	}
	return res;
}
void real_add(int a,int b,int x,int y,int d)
{
   
	add(a,b,d);
	add(x+1,b,-d);
	add(a,y+1,-d);
	add(x+1,y+1,d);
}
int realqr(int a,int b,int x,int y)
{
   
	return  qr(x,y)-qr(a-1,y)-qr(x,b-1)+qr(a-1,b-1);
}
signed main()
{
   
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int op;
	while(cin>>op)
	{
   
		if(op==1)
		{
   
			int a,b,c,d,e;
			cin>>a>>b>>c>>d>>e;
			real_add(a,b,c,d,e);
		}
		else if(op==2)
		{
   
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			cout<<realqr(a,b,c,d)<<endl;	
		}
	}
}