Segment Tree Modify

Analysis: Given an index and a value, replace indexed node's max attribute with the new value.

Finding the indexed node and replacing its max attribute is easy, the difficulty is how to make sure the resultant segment tree is still valid.

Segment Tree Modification is similar to the query problem, we can still conclude all the situations which could happen. The difference is that we only have one index here, so there will not be the situation of across mid point.

Mention: The new replacing value could be both larger and smaller that the previous value.

Solution: Actual update of max attributes to the nodes is caused by top-down recursion. Need to check or update a path of nodes from root to the indexed leaf node.

public void modify(SegmentTreeNode root, int index, int value) {
        // When root is null
        if (root == null)
            return;
        // Index resides outside the root's range
        if (index < root.start || index > root.end)
            return;
        // Leaf node match
        if (index == root.start && index == root.end){
            root.max = value;
            return;
        }

        // When the index resides inside the root's range
        int mid = (root.start+root.end)/2;

        if (index <= mid){
            modify(root.left, index, value);
        }
        else{
            modify(root.right, index, value);
        }
        root.max = Math.max(root.left.max, root.right.max);
    }