Untitled

class NumMatrix {
    // Prefix sum matrix to store cumulative sums
    private int[][] prefixSum;

    // Constructor to initialize the prefix sum matrix
    public NumMatrix(int[][] matrix) {
        // Handle edge case: empty matrix
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;

        int rows = matrix.length;
        int cols = matrix[0].length;

        // Initialize the prefix sum matrix with the same dimensions as the input matrix
        prefixSum = new int[rows][cols];

        // Build the prefix sum matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Start with the current value from the original matrix
                prefixSum[i][j] = matrix[i][j];

                // Add the sum from the row above (if it exists)
                if (i > 0) {
                    prefixSum[i][j] += prefixSum[i - 1][j];
                }

                // Add the sum from the column to the left (if it exists)
                if (j > 0) {
                    prefixSum[i][j] += prefixSum[i][j - 1];
                }

                // Subtract the overlap (if both row and column exist)
                if (i > 0 && j > 0) {
                    prefixSum[i][j] -= prefixSum[i - 1][j - 1];
                }
            }
        }
    }

    // Method to calculate the sum of a submatrix
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // Start with the bottom-right corner of the rectangle
        int total = prefixSum[row2][col2];

        // Subtract the sum above the rectangle (if it exists)
        if (row1 > 0) {
            total -= prefixSum[row1 - 1][col2];
        }

        // Subtract the sum to the left of the rectangle (if it exists)
        if (col1 > 0) {
            total -= prefixSum[row2][col1 - 1];
        }

        // Add back the overlap (if both row and column exist)
        if (row1 > 0 && col1 > 0) {
            total += prefixSum[row1 - 1][col1 - 1];
        }

        // Return the computed sum
        return total;
    }
}