前缀和
cpp
//一维
void init(){
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
}
int query(int l,int r){
return sum[r]-sum[l-1];
}
//二维
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
}
int query(int x,int y,int xx,int yy){
return sum[xx][yy]-sum[xx][y-1]-sum[x-1][yy]+sum[x-1][y-1];
}