解法
代码
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] one = br.readLine().split(" ");
int n=Integer.parseInt(one[0]),m=Integer.parseInt(one[1]),k=Integer.parseInt(one[2]);
int[][] preSums = new int[n+1][m+1]; //为了更好的统一二维前缀和算法的公式(更好的处理边界),这里我们把前缀和矩阵行列都扩充1
//填充前缀和矩阵。
for(int i=1;i<=n;i++){//从[1][1]开始
String[] strs = br.readLine().split(" ");
for(int j=1;j<=m;j++){
preSums[i][j] = preSums[i-1][j] + preSums[i][j-1] - preSums[i-1][j-1] + Integer.parseInt(strs[j-1]); //当前位置的前缀和等于左边的前缀和加上上面的前缀和,然后减去左上角的前缀和,最后加上自己位置的数值。
}
}
//开始询问
for(int i=0;i<k;i++){
String[] strs = br.readLine().split(" ");
int x1 = Integer.parseInt(strs[0]),y1=Integer.parseInt(strs[1]),x2 = Integer.parseInt(strs[2]),y2 = Integer.parseInt(strs[3]);
int res = preSums[x2][y2] - preSums[x2][y1-1] - preSums[x1-1][y2] + preSums[x1-1][y1-1]; //长方形的和等于 右下角的前缀和 减去 左下角左边一位的前缀和 减去右上角的上面一位的前缀和 最后加上长方形左上角的左上角的那个位置的前缀和即可。
System.out.println(res);
}
br.close();
}
}
评析
这是二维前缀和算法的经典例题。
前缀和算法中的两个核心操作:构造前缀和数组 + 计算区间长度/面积操作。对应的就是代码中的15行与22行。
代码中值得注意的就是为了防止边界问题/统一公式 让前缀和矩阵都扩充了一个维度。