首先说明一下，看这个博客之前，最好有线段树的基本概念，比如说线段树的构造、线段树的查询之类的。
最近在学习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;
}
}
}
}
