Leetcode discuss: 308. Range Sum Query 2D - Mutable

 Here is the link. 

First practice - C# - copy and learn

Dec. 7, 2020
I will take some time later to figure out what is challenge for this algorithm. I like to practice first using prefix sum, and also every time Update API is called, row prefix sum is updated accordingly.

public class NumMatrix {

    private int[][] rowPrefix;
    private int[][] matrix;
    private int rows;
    private int cols;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.rows = matrix.Length;
        this.cols = rows > 0 ? matrix[0].Length : 0;
        
        this.rowPrefix = new int[rows][];
        
        for (int row = 0; row < rows; row++)
        {
            rowPrefix[row] = new int[cols];
            
            updateRowPrefix(row, 0);
        }
    }      
    
    public void Update(int row, int col, int val) 
    {
        matrix[row][col] = val;
        updateRowPrefix(row, col);
    }      
    
    public int SumRegion(int row1, int col1, int row2, int col2) {
        var sum = 0;
        for (int row = row1; row <= row2; row++)
        {
            sum += getSumRow(row, col1, col2);
        }
        return sum;
    }
    
    /// support function 
    private int getSumRow(int row, int cFrom, int cTo)
    {
        var sumTo = rowPrefix[row][cTo];
        var sumFrom = cFrom > 0 ? rowPrefix[row][cFrom - 1] : 0;
        var answer = sumTo - sumFrom;
        return answer;
    }
    
    private void updateRowPrefix(int r, int c)
    {
        var sum = c > 0 ? rowPrefix[r][c - 1] : 0;
        
        for (int col = c; col < cols; col++)
        {
            sum += matrix[r][col];
            rowPrefix[r][col] = sum;
        }
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.Update(row,col,val);
 * int param_2 = obj.SumRegion(row1,col1,row2,col2);
 */