Java Segment Tree solution


  • 1
    D
     public static class SegmentTreeNode {
        public int start, end, sum;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
    }
    
    private SegmentTreeNode root;
    
    void update(int i, int val) {
        updateTree(i, val, root);
    }
    
    public RangeSumQueryMutable(int[] nums) {
        root = buildTreeNode(nums, 0, nums.length - 1);
    }
    
    
    public int sumRange(int i, int j) {
        return treeSum(i, j, root);
    }
    
    private int treeSum(int start, int end, SegmentTreeNode root) {
        if(root == null || start > root.end || end < root.start) return 0;
        if(start == root.start && end == root.end) return root.sum;
        int leftSum = root.left == null ? 0 : treeSum(Math.max(root.left.start, start), Math.min(root.left.end, end), root.left);
        int rightSum = root.right == null ? 0 : treeSum(Math.max(root.right.start, start), Math.min(root.right.end, end), root.right);
        return leftSum + rightSum;
    }
    
    private SegmentTreeNode buildTreeNode(int[] nums, int start, int end) {
        if(start > end) return null;
        if(start == end) return new SegmentTreeNode(start, end, nums[start]);
        SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
        int mid = start + (end - start) / 2;
        root.left = buildTreeNode(nums, start, mid);
        root.right = buildTreeNode(nums, mid + 1, end);
        root.sum = (root.left == null ? 0 : root.left.sum) + (root.right == null ? 0 : root.right.sum);
        return root;
    }
    
    private void updateTree(int index, int val, SegmentTreeNode root) {
        if(root.start > index || root.end < index) return;
        int start = root.start;
        int end = root.end;
        if(start == end) {
            root.sum = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if(index > mid) updateTree(index, val, root.right);
        else updateTree(index, val, root.left);
        root.sum = (root.left == null ? 0 : root.left.sum) + (root.right == null ? 0 : root.right.sum);
    }

Log in to reply
 

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