二维前缀和

二维前缀和

class MatrixSum {
private final int[][] sum;

public MatrixSum(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    sum = new int[m + 1][n + 1]; // 注意：如果 matrix[i][j] 范围很大，需要使用 long
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
        }
    }
}

// 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）
public int query(int r1, int c1, int r2, int c2) {
    return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
}

// 如果你不习惯左闭右开，也可以这样写
// 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和
public int query2(int r1, int c1, int r2, int c2) {
    return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
}

}

感谢灵神
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/UUuRex/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。