307. Range Sum Query - Mutable

/*
Using Segment Tree

Time Complexity:
1. NumArray = O(N)
2. update = O(log N)
3. sumRange = O(log N)

Space Complexity: O(N)

Space ranges from 2N to 4N.
Refer : https://www.youtube.com/watch?v=ZBHKZF5w4YU
*/
class NumArray {

    private class SegmentTreeNode {
        int start;
        int end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;

        SegmentTreeNode (int s, int e) {
            start = s;
            end = e;
        }
    }

    SegmentTreeNode root;

    public NumArray(int[] nums) {
        root = buildTree(nums, 0, nums.length-1);
    }

    private SegmentTreeNode buildTree(int[] nums, int s, int e) {
        if (s > e) {
            return null;
        }
        SegmentTreeNode node = new SegmentTreeNode(s, e);
        if (s == e) {
            node.sum = nums[s];
        } else {
            int mid = s + (e-s)/2;
            node.left = buildTree(nums, s, mid);
            node.right = buildTree(nums, mid+1, e);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

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

    private void updateTree(SegmentTreeNode node, int i, int val) {
        if (node.start == node.end && node.start == i) {
            node.sum = val;
            return;
        }
        int mid = node.start + (node.end - node.start)/2;
        if (i <= mid) {
            updateTree(node.left, i, val);
        } else {
            updateTree(node.right, i, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }

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

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

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */