For aMaximum Segment Tree, which each node has an extra valuemaxto store the maximum value in this node's interval.

Implement amodifyfunction with three parameterroot,indexandvalueto change the node's value with_[start, end] = [index, index]_to the new given value. Make sure after this change, every node in segment tree still has themaxattribute with the correct value.

Notice

We suggest you finish problemSegment Tree BuildandSegment Tree Queryfirst.

Have you met this question in a real interview?

Yes

Example

For segment tree:

                      [1, 4, max=3]
                    /                \
        [1, 2, max=2]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]

if callmodify(root, 2, 4), we can get:

                      [1, 4, max=4]
                    /                \
        [1, 2, max=4]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]

orcallmodify(root, 4, 0), we can get:

                      [1, 4, max=2]
                    /                \
        [1, 2, max=2]                [3, 4, max=0]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]

先遍历到Index

然后回溯更新

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of segment tree.
     * @param index: index.
     * @param value: value
     * @return: 
     */
    public void modify(SegmentTreeNode root, int index, int value) {
        // write your code here
        if (root == null) {
            return;
        }

        if (root.start == root.end && root.start != index) {
            return;
        }

        if (root.start == root.end && root.start == index) {
            root.max = value;
            return;
        }

        int mid = (root.start + root.end) / 2;

        if (index <= mid) {
            modify(root.left, index, value);

        } else {
            modify(root.right, index, value);
        }

        //no need to check if null always has left and right
        root.max = Math.max(root.right.max, root.left.max);
    }
}