与求sum的线段树不同
http://blog.csdn.net/ice110956/article/details/12067537
区间最值问题：
有如下无序序列，求任意子区间段的最大值。
接着，我们要用分治的思想来快速地解决上面的问题。在解决问题之前，先介绍一些分治的概念。
二分查找
二分查找是分治思想的典型运用
我们有如下序列：
A1,A2,A3……An.
要查找其中等于b的元素。一种方法就是一个个对比，看看是不是相等，时间复杂度为N。还有就是二分查找。
如上图，通过不断地与中间元素对比，缩小搜索区间，最后得到A4==b.时间复杂度为logN.
二叉搜索树
在二分查找中，我们要求队列是有序地。那么如果队列无序又要如何？我们可以仿造二分查找的方式，构造一个二叉搜索树，如下：
二叉搜索树左节点比根小，右节点比根大。上图红色箭头代表搜索A4的过程。
线段树
线段树也是一种二叉搜索树，我们回到区间最值的问题，有如下无序序列
现在我们要在上面的序列中，搜索任意指定区间的最大值。
我们先来解决总的最大值的问题
一个基本的方法就是一个个比较，取出最大值，时间复杂度为N。
我们借用二分搜索的分治思想。可以把序列划分为1-5节点的最大值和6-8的最大值，再取这两个值的较大值。递归地，我们再把1-5继续划分至只剩一个元素。这样的时间复杂度为logN .如下面的过程，即线段数搜索的过程：
上面的过程就是选取区间最大值的方式，总的最大值为9.
接着，我们要处理任意指定子序列的最值问题。
根据上图我们可以看出，根据中间的结果，可以和容易地寻找1-6个节点的最大值，分治为1-4的最大值7，5-6的最大值8,1-6的最大值就为8.
总结一下上述的思想。
首先，有点像总统选举，我们要寻找一个国家最适合当总统的人，不需要一个个去比较，只需要每个乡选一个最好的，再在县里比较，得出一个县里最好的，然后市，然后省，最后我们得到了全国最好的。
然后，我们选举的过程中，得到了乡，县的中间结果，这些又可以用来选取任意小范围的最好人选。如我们要选总管广东，广西和南京鼓楼区第二大街的总管，只需要用到不同级别的中间结果汇总即可。
线段树最终回到分治的思想上来，其应用与如下领域：
区间最值查询问题
连续区间修改或者单节点更新的动态查询问题
多维空间的动态查询
线段树的编程实践：
线段树的节点结构为：
其中max保存当前线段的最大值。
线段树最基本要有三个函数：
1.递归地建立树：
2.递归地插入：
3.递归地查询：
最后，求解任意区间最值的代码如下：
