5-前缀和

算法思想

1. 计算出前缀和
2. 使用前缀和求解区间问题

一维前缀和

// a为普通数组，s 为 a 的前缀和数组
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

S[i, j] = 第 i 行 j 列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

算法细节

二维前缀和

• 需要补0，才能找出前缀和求解的规律

算法图解

算法模板

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        
        int[][] a = new int[n + 1][m + 1];
        int[][] s = new int[n + 1][m + 1];
        
        // 初始化数组
        // 方便起见，不使用下标0
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                a[i][j] = sc.nextInt();

                // 需要补0，才能发现此规律
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
            }
        }
        
        while(q -- > 0){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            
            int result = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];;
            System.out.println(result);;
        }
    }
}