Java 2D Binary-indexed-tree solution 80ms


  • 0
    B

    For binary indexed tree information, please refer to the Topcoder tutorial:

    https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

    The code below is just a 2D version of that. About 80-90 ms run-time in Java.

    public class NumMatrix {
    
        int[][] tree;
    	int MaxValRow, MaxValCol;
    	
    	public NumMatrix(int[][] matrix) {
    		if (matrix == null || matrix.length == 0)
    			return;
    		MaxValRow = matrix.length;
    		MaxValCol = matrix[0].length;
            tree = new int[MaxValRow + 1][MaxValCol + 1];            
            for (int i = 0; i < MaxValRow; i++) {
            	for (int j = 0; j < MaxValCol; j++) {
            		changeSingle(i + 1, j + 1, matrix[i][j]);
            	}        	
            } 
    	}
    	
    	public void update(int row, int col, int val) {
    		changeSingle(row + 1, col + 1, val - readSingle(row + 1, col + 1));
    	}
    	
    	public int sumRegion(int row1, int col1, int row2, int col2) {
    		return readSum(row2 + 1, col2 + 1) + readSum(row1, col1) - readSum(row2 + 1, col1) - readSum(row1, col2 + 1);
    	}
    	
    	private int readSum(int row, int col) {
    		List<Integer> rowList = new ArrayList<Integer>();
    		List<Integer> colList = new ArrayList<Integer>();
    		int sum = 0;
            while (row > 0){
                rowList.add(row);
                row -= (row & -row);
            }
            while (col > 0){
                colList.add(col);
                col -= (col & -col);
            }
            for (Integer i : rowList) {
            	for (Integer j : colList) {
            		sum += tree[i][j];
            	}
            }
            return sum;
    	}
    	
    	private void changeSingle(int row, int col, int val) {
    		List<Integer> rowList = new ArrayList<Integer>();
    		List<Integer> colList = new ArrayList<Integer>();
    		while (row <= MaxValRow) {
    			rowList.add(row);
                row += (row & -row);
            }
    		while (col <= MaxValCol) {
    			colList.add(col);
                col += (col & -col);
            }
    		for (Integer i : rowList) {
            	for (Integer j : colList) {
            		tree[i][j] += val;
            	}
            }
    	}
    	
    	private int readSingle(int row, int col) {
    		int z, rowB = row, colB = col;
    		List<Integer> rowList = new ArrayList<Integer>();
    		List<Integer> colList = new ArrayList<Integer>();
    		z = row - (row & -row);
    	    row--;
    	    while (row != z) {
    	    	rowList.add(row);
    	        row -= (row & -row);
    	    }
    	    z = col - (col & -col);
    	    col--;
    	    while (col != z) {
    	    	colList.add(col);
    	        col -= (col & -col);
    	    }
    	    row = rowB; col = colB;
    	    int sum = tree[row][col];
    	    for (Integer j : colList) {
    	    	sum -= tree[row][j];
    	    }
    	    for (Integer i : rowList) {
    	    	sum -= tree[i][col];
    	    }
    	    for (Integer i : rowList) {
    	    	for (Integer j : colList) {
    	    		sum += tree[i][j];
    	    	}
    	    }
    	    return sum;
    	}
    }

Log in to reply
 

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