struct NumMatrix {
    sums_matrix: Vec<Vec<i32>>
}


/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl NumMatrix {
    // Generate an accumulating sum matrix in-place
    // O(1) extra memory
    fn new(mut matrix: Vec<Vec<i32>>) -> Self {
        for row in (0..matrix.len()) {
            let mut acc = 0;
            for col in (0..matrix[0].len()) {
                acc += matrix[row][col];
                matrix[row][col] = acc;
                if row != 0 {
                    matrix[row][col] += matrix[row-1][col];
                }
            }
        }
        NumMatrix { sums_matrix: matrix }
    }
    
    // Use the accumulating sums to get the sum of the region
    // Space: O(1), Time: O(1)
    fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
        let top_rec = if row1 == 0 { 0 } else { self.sums_matrix[row1 as usize - 1][col2 as usize] };
        let left_rec = if col1 == 0 { 0 } else { self.sums_matrix[row2 as usize][col1 as usize - 1] };
        let rec_overlap = if row1 == 0 || col1 == 0 { 0 } else { self.sums_matrix[row1 as usize - 1][col1 as usize - 1] };
        self.sums_matrix[row2 as usize][col2 as usize] - top_rec - left_rec + rec_overlap
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * let obj = NumMatrix::new(matrix);
 * let ret_1: i32 = obj.sum_region(row1, col1, row2, col2);
 */