RangeSumQueryMutable.java

package medium;

public class RangeSumQueryMutable {
        
    public static void main(String...strings){
//        int[] nums = new int[]{1,3,5};
        
        int[] nums = new int[]{7,2,7,2,0};
        NumArray test = new NumArray(nums);
        test.update(4,6);
        test.update(0,2);
        test.update(0,9);
    }
}

class NumArray {
    class SegmentTreeNode{
        SegmentTreeNode left;
        SegmentTreeNode right;
        int start;
        int end;
        int sum;
        
        public SegmentTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            this.left = null;
            this.right = null;
            this.sum = 0;
        }
    }
    
    private SegmentTreeNode root = null;

    public NumArray(int[] nums) {
        root = buildSegmentTree(nums, 0, nums.length-1);
    }
    
    SegmentTreeNode buildSegmentTree(int[] nums, int start, int end){
        if(start > end){
            return null;
        } else {
            SegmentTreeNode root = new SegmentTreeNode(start, end);
            if(start == end){
                root.sum = nums[start];
            } else {
                int mid = start + (end-start)/2;
                root.left = buildSegmentTree(nums, start, mid);
                root.right = buildSegmentTree(nums, mid+1, end);
                root.sum = root.left.sum + root.right.sum;
            }
            return root;
        }
    }

    void update(int i, int val) {
        update(root, i, val);
    }
    
    void update(SegmentTreeNode root, int pos, int val){
        if(root.start == root.end){
            root.sum = val;
        } else {
            int mid = root.start + (root.end - root.start)/2;
            if(pos <= mid){
                update(root.left, pos, val);
            } else {
                update(root.right, pos, val);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
    
    int sumRange(SegmentTreeNode root, int start, int end){
        if(root.end == end && root.start == start){
            return root.sum;
        } else {
            int mid = root.start + (root.end-root.start)/2;
            if(end <= mid){
                return sumRange(root.left, start, end);
            } else if(start >= mid+1){
                return sumRange(root.right, start, end);
            } else {
                return sumRange(root.right, mid+1, end) + sumRange(root.left, start, mid);
            }
        }
    }
}