1.思路

直接看图就可以推出公式。

我们这里继续用原数组当作前缀和数组。

前缀和计算：s[i] [j] = s[i - 1] [j] + s[i] [j - 1] - s[i - 1] [j - 1] + in.nextInt();

子矩阵的和：s[x2] [y2] - s[x1 - 1] [y2] - s[x2] [y1 - 1] + s[x1 - 1] [y1 - 1];

2.代码模板

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] s = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++) 
            for(int j = 1; j <= m; j++)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + in.nextInt();
        while (q-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            int ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(ans);
        }
    }
}

3.复杂度分析

• 时间复杂度:O(n^2)
• 空间复杂度:O(n^2)