C# with Binary Index Tree


  • 0
    H
    public class NumMatrix {
        int[,] bit, vals;
        int n, m;
    
        public NumMatrix(int[,] matrix) {
            m = matrix.GetLength(0);
            n = matrix.GetLength(1);
            
            bit = new int [m + 1, n + 1];
            vals = new int [m, n];
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    Update(i, j, matrix[i, j]);
                }
            }
        }
        
        public void Update(int row, int col, int val) {
            int d = val - vals[row, col];
            vals[row, col] = val;
            for(int i = row + 1; i <= m; i += (i & -i)) {
                for(int j = col + 1; j <= n; j += (j & -j)) {
                    bit[i, j] += d;
                }    
            }
        }
        
        public int SumRegion(int row1, int col1, int row2, int col2) {
            return OriginSum(row2, col2) + OriginSum(row1 - 1, col1 - 1) - OriginSum(row2, col1 - 1) - OriginSum(row1 - 1, col2);
        }
        
        public int OriginSum(int row, int col) {
            int sum = 0;
            for(int i = row + 1; i > 0; i -= (i & -i)) {
                for(int j = col + 1; j > 0; j -= (j & -j)) {
                    sum += bit[i, j];
                }    
            }
            
            return sum;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.