首先说明一下，看这个博客之前，最好有线段树的基本概念，比如说线段树的构造、线段树的查询之类的。
最近在学习ANdroid IPC，所以有几天没在LintCode上面做面试题，今天晚上恰巧有空，做了一道题。线段树在这之前，我认真的学习了一遍，其实我也是初学线段树，之前在别人的博客上学习。这里我就不在详细的讲解线段树，因为网络上那些大佬比我讲的更加清楚，我在推荐一下一个大佬的博客：浅谈线段树。我就是在这个博客上学习的。
  废话说的有点多，直接进入今天的主题。

题意：

对于一棵 最大线段树, 每个节点包含一个额外的 max 属性，用于存储该节点所
代表区间的最大值。

设计一个 modify 的方法，接受三个参数 root、 index 和 value。该方法将 
root 为根的线段树中 [start, end] = [index, index] 的节点修改为了新的 
value ，并确保在修改后，线段树的每个节点的 max 属性仍然具有正确的值。

样例：

对于线段树:

                      [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]
如果调用 modify(root, 2, 4), 返回:

                      [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]

或 调用 modify(root, 4, 0), 返回:

                      [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]

  乍一看，这个题不是非常的简单吗？是啊，非常的简单，使用递归的方式是非常的简单的。

1.递归

  递归的方式非常的简单，这里就不在讲解，直接看代码

public void modify(SegmentTreeNode root, int index, int value) {
        if (index > root.end || index < root.start) {
            return;
        }
        //当找到那个那个点了，更新max值
        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);
        }
        //更新root节点本身，这一点非常的重要，因为子树的max值改了
        //root的max有可能会改变
        root.max = Math.max(root.left.max, root.right.max);
    }

2.非递归的方式(o(n)的时间复杂度)

  有人有疑问，为什么递归的方式都能简单的解决问题，为什么我们偏要将问题想得非常的复杂。其实，这个题有一个挑战项，就是在O(n)的复杂度里面解决这种问题。
  遇到这种需求，才开始，我也是一脸懵逼的，但是经过后来借鉴了别人的思想，能成功的理解，并且写出完整的代码。
  首先，我来解释这种方式的思路：

  (1).当value > root.max时，这种情况下，root的max肯定是value。因此这种情况，也是非常容易的解决的。使用循环遍历，更新每一个点的max值就行了。

  (2).当value <= root.max时，这种情况下，我们首先只能更新目标节点的max值，然后更新目标节点的上层节点，直到更新到root节点。感觉这里非常的麻烦，怎么更新上层节点的值呢？这里的方法相对来说比较巧妙。

public void modify(SegmentTreeNode root, int index, int value) {
        if (root == null || index > root.end || index < root.start) {
            return;
        }
        SegmentTreeNode node = root;
        //当value大于root.max,直接更新
        if (value > node.max) {
            while (node.left != null) {
                node.max = value;
                int mid = (node.end + node.start) / 2;
                if (index <= mid) {
                    node = node.left;
                } else {
                    node = node.right;
                }
            }
            node.max = value;
        } else {
            
            while (node.left != null) {
                int mid = (node.end + node.start) / 2;
                if (index <= mid) {
                    node = node.left;
                } else {
                    node = node.right;
                }
            }
            //先只更新目标节点的值
            node.max = value;
            
            SegmentTreeNode node1 = root;
            while (node != root) {
                node1 = root;
                //找到node节点的上一层节点
                while (node1.left != node && node1.right != node) {
                    int mid = (node1.end + node1.start) / 2;
                    if (index <= mid) {
                        node1 = node1.left;
                    } else {
                        node1 = node1.right;
                    }
                }
                //获得最大值
                int max = Math.max(node1.left.max, node1.right.max);
                if (max == node1.max) {
                    break;
                } else {
                    //更新max值，并且将node节点改变成node节点的上层节点
                    node1.max = max;
                    node = node1;
                }
            }
        }
    }