Range Sum Query

lc 303

Range Sum Query - Immutable

public class NumArray {
    int[] sum;

    public NumArray(int[] nums) {
        if(nums == null || nums.length == 0) return;
        sum = new int[nums.length];
        sum[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum[i] = sum[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        if( i > j || i > sum.length || j > sum.length) return 0;
        if(i == 0 ) return sum[j];
        return sum[j] - sum[i - 1];
    }
}

lc 304 Range Sum Query 2D - Immutable

public class NumMatrix {
    int [][] sum;

    public NumMatrix(int[][] matrix) {
        if(matrix==null || matrix.length==0||matrix[0].length==0)
            return;

        int m = matrix.length;
        int n = matrix[0].length;
        sum = new int[m][n];

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

            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(this.sum==null) 
            return 0;

        int topRightX = row1;
        int topRightY = col2;

        int bottomLeftX=row2;
        int bottomLeftY= col1;

        int result=0;

        if(row1==0 && col1==0){
            result = sum[row2][col2];
        }else if(row1==0){
            result = sum[row2][col2]
                    -sum[bottomLeftX][bottomLeftY-1];

        }else if(col1==0){
            result = sum[row2][col2]
                    -sum[topRightX-1][topRightY];
        }else{
            result = sum[row2][col2]
                    -sum[topRightX-1][topRightY]
                    -sum[bottomLeftX][bottomLeftY-1]
                    +sum[row1-1][col1-1];
        }

        return result;
    }
}

lc 307 Range Sum Query - Mutable

class TreeNode{
    int start;
    int end;
    int sum;
    TreeNode left;
    TreeNode right;

    public TreeNode(int start, int end, int sum){
        this.start = start;
        this.end = end;
        this.sum = sum;
    }

    public TreeNode(int start, int end){
        this.start = start;
        this.end = end;
        this.sum = 0;
    }   

}
public class NumArray {

    TreeNode root = null;

    public NumArray(int[] nums) {
        if(nums == null || nums.length == 0) return;
        this.root = builderTree(nums, 0, nums.length - 1);
    }

    public TreeNode builderTree(int[] nums, int start, int end){
        if(nums == null || nums.length == 0 || start > end) return null;
        if(start == end) return new TreeNode(start, end, nums[start]);
        int mid = start + (end - start) / 2;

        TreeNode current = new TreeNode(start, end);

        current.left = builderTree(nums, start, mid);
        current.right = builderTree(nums, mid + 1, end);
        current.sum = current.left.sum + current.right.sum;
        return current;

    }
    void update(int i, int val) {
        updateHelper(root, i, val);

    }

    public void updateHelper(TreeNode cur, int i, int val){
        if(cur == null) return;
        if(cur.start > i || cur.end < i) return;
        if(cur.start == cur.end && cur.start == i){
            cur.sum = val;
            return;
        }        
        int mid = cur.start + (cur.end - cur.start) / 2;
        if(i > mid){
            updateHelper(cur.right,i, val);
        }else{
            updateHelper(cur.left, i, val);
        }

        cur.sum = cur.right.sum + cur.left.sum;
    }

    public int sumRange(int i, int j) {
        return sumRangeHelper(root, i, j);
    }

    public int sumRangeHelper(TreeNode cur, int i, int j){
        if(cur == null) return 0;
        if(cur.start> j || cur.end < i) return 0;
        if(cur.start >= i && cur.end <= j) return cur.sum;
        return sumRangeHelper(cur.left, i, j) + sumRangeHelper(cur.right, i , j);


    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

lc 308 2d immutable

TreeNode root;
public NumMatrix(int[][] matrix) {
    if (matrix.length == 0) {
        root = null;
    } else {
        root = buildTree(matrix, 0, 0, matrix.length-1, matrix[0].length-1);
    }
}

public void update(int row, int col, int val) {
    update(root, row, col, val);
}

private void update(TreeNode root, int row, int col, int val) {
    if (root.row1 == root.row2 && root.row1 == row && root.col1 == root.col2 && root.col1 == col) {
        root.sum = val;
        return;
    }
    int rowMid = (root.row1 + root.row2) / 2;
    int colMid = (root.col1 + root.col2) / 2;
    TreeNode next;
    if (row <= rowMid) {
        if (col <= colMid) {
            next = root.c1;
        } else {
            next = root.c2;
        }
    } else {
        if (col <= colMid) {
            next = root.c3;
        } else {
            next = root.c4;
        }
    }
    root.sum -= next.sum;
    update(next, row, col, val);
    root.sum += next.sum;
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    return sumRegion(root, row1, col1, row2, col2);
}

private int sumRegion(TreeNode root, int row1, int col1, int row2, int col2) {
    if (root.row1 == row1 && root.col1 == col1 && root.row2 == row2 && root.col2 == col2)
        return root.sum;
    int rowMid = (root.row1 + root.row2) / 2;
    int colMid = (root.col1 + root.col2) / 2;
    if (rowMid >= row2) {
        if (colMid >= col2) {
            return sumRegion(root.c1, row1, col1, row2, col2);
        } else if (colMid + 1 <= col1) {
            return sumRegion(root.c2, row1, col1, row2, col2);
        } else {
            return sumRegion(root.c1, row1, col1, row2, colMid) + sumRegion(root.c2, row1, colMid+1, row2, col2);
        }
    } else if (rowMid + 1 <= row1) {
        if (colMid >= col2) {
            return sumRegion(root.c3, row1, col1, row2, col2);
        } else if (colMid + 1 <= col1) {
            return sumRegion(root.c4, row1, col1, row2, col2);
        } else {
            return sumRegion(root.c3, row1, col1, row2, colMid) + sumRegion(root.c4, row1, colMid+1, row2, col2);
        }
    } else {
        if (colMid >= col2) {
            return sumRegion(root.c1, row1, col1, rowMid, col2) + sumRegion(root.c3, rowMid+1, col1, row2, col2);
        } else if (colMid + 1 <= col1) {
            return sumRegion(root.c2, row1, col1, rowMid, col2) + sumRegion(root.c4, rowMid+1, col1, row2, col2);
        } else {
            return sumRegion(root.c1, row1, col1, rowMid, colMid) + sumRegion(root.c2, row1, colMid+1, rowMid, col2) + sumRegion(root.c3, rowMid+1, col1, row2, colMid) + sumRegion(root.c4, rowMid+1, colMid+1, row2, col2);
        }
    }
}

private TreeNode buildTree(int[][] matrix, int row1, int col1, int row2, int col2) {
    if (row2 < row1 || col2 < col1)
        return null;
    TreeNode node = new TreeNode(row1, col1, row2, col2);
    if (row1 == row2 && col1 == col2) {
        node.sum = matrix[row1][col1];
        return node;
    }
    int rowMid = (row1 + row2) / 2;
    int colMid = (col1 + col2) / 2;
    node.c1 = buildTree(matrix, row1, col1, rowMid, colMid);
    node.c2 = buildTree(matrix, row1, colMid+1, rowMid, col2);
    node.c3 = buildTree(matrix, rowMid+1, col1, row2, colMid);
    node.c4 = buildTree(matrix, rowMid+1, colMid+1, row2, col2);
    node.sum += node.c1 != null ? node.c1.sum : 0;
    node.sum += node.c2 != null ? node.c2.sum : 0;
    node.sum += node.c3 != null ? node.c3.sum : 0;
    node.sum += node.c4 != null ? node.c4.sum : 0;
    return node;
}

public class TreeNode {
    int row1, row2, col1, col2, sum;
    TreeNode c1, c2, c3, c4;
    public TreeNode (int row1, int col1, int row2, int col2) {
        this.row1 = row1;
        this.col1 = col1;
        this.row2 = row2;
        this.col2 = col2;
        this.sum = 0;
    }
}