class NumMatrix {

    int sum[][];
    int m;
    int n;
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m ==0)
            return;
        n = matrix[0].length;
        sum = new int[m][n];
        for(int i =0;i<n;i++)
        {
            sum[0][i] = matrix[0][i];
        }

        //Now do column wise sum

        for(int i =1;i<m;i++)
        {
            for(int j =0;j<n;j++)
            {
                sum[i][j] = matrix[i][j] + sum[i-1][j];
            }
        }

        //Now do row wise sum
        for(int i =0;i<m;i++)
        {
            for(int j =1;j<n;j++)
            {
                sum[i][j] = sum[i][j] + sum[i][j-1];
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1>0 && col1>0)
            return sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1];
        else if(row1==0 && col1>0)
        {
            return sum[row2][col2] - sum[row2][col1-1];
        }
        else if(row1>0 && col1==0)
        {
            return sum[row2][col2] - sum[row1-1][col2];
        }
        else{
            return sum[row2][col2];
        }
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */