why

利用算法求矩阵的合

how

理论

1.如何构造前缀和矩阵

xy各退一想加，减去xy全退一，加右下角
image.png

2.如何计算子矩阵的合

总矩阵减去一个L，再加回左上角。
通过左上右下来确定子矩阵方位

image.png
`SS+ SS+ a```
image.png

代码

1.记住理论的两张图作为记忆线索
2.x行，y列。数组[行][列]。
3.通过左上坐标，右下坐标来确定子矩阵方位

  1. package lanqiaobei.二分和前缀;
  2. import java.util.Scanner;
  4. public class juzhen {
  5.     static int[][] raw;
  6.     static int[][] add;
  7.     static int q;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         int x = sc.nextInt();
  12.         int y = sc.nextInt();
  13.         int q = sc.nextInt();
  14.         raw = new int[x+1][y+1];
  15.         add = new int[x+1][y+1];
  16.         for (int i = 1; i <= x; i++) {
  17.             for (int j = 1; j <= y; j++) {
  18.                 raw[i][j] = sc.nextInt();
  19.                 /*构造前缀和数组*/
  20.                 add[i][j] = add[i-1][j] + add[i][j-1] - add[i-1][j-1] + raw[i][j];
  21.             }
  22.         }
  23.         for (int i = 0; i < q; i++) {
  24.             int x1 = sc.nextInt();
  25.             int y1 = sc.nextInt();
  26.             int x2 = sc.nextInt();
  27.             int y2 = sc.nextInt();
  28.             int child = add[x2][y2] - add[x1-1][y2] - add[x2][y1-1] - add[x1-1][y1-1];
  29.             System.out.println(child);
  30.         }
  32.     }
  33. }

what