树状数组的前缀和,差分的话好像有点不太一样?
修改和查询的时间复杂度应该都是$log_2^2n$
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int tr[N][N];
int n,m,t;
int lowbit(int x){
return x&-x;
}
void add(int a,int b,int x){
for(int i=a;i<=n;i+=lowbit(i))
for(int j=b;j<=m;j+=lowbit(j))
tr[i][j]+=x;
}
int sum(int x,int y){
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=tr[i][j];
return ans;
}
int main(){
cin>>n>>m>>t;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x;
cin>>x;
add(i,j,x);
}
while(t--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)<<endl;
}
}