线段树，其实我很不理解为什么叫做线段树。不就是一棵二叉树嘛，好端端的为啥非要给起个名字叫线段树，搞得我翻了那么多资料，最后看了MIT的视频，才算搞清楚了个大概，而且其实人家MIT讲的还是interval tree，跟线段树并不完全一样。

线段树的主要思想就是利用满二叉树来储存数据。由于满二叉树的高度是O(logN)的，操作一般可以O(logN)时间内完成。因此，只要对二叉树进行适当的修改和扩充，就可以高效地在对数时间实现所要求的操作。具体对于这道题目而言，每个节点需要维护一段连续数据中的最大值和最小值，以及这段数据的起始和终止位置；再把这段数据砍为两截，左儿子便对应了左边一截的最大值和最小值，右儿子自然对应右边一截。举个例子，如果有X1,X2,...,X10一共10个数据的话，那么根里面储存的就是1和10两个下标，外加X1到X10的最大值和最小值；根的左儿子储存1、5以及X1到X5的最大最小值，X6到X10的信息则由右儿子储存；以此类推。树这么递归地往下生长，到了叶子一层，存的都是Xi到Xi的最大值和最小值，其实就是数据本身了。显然，在这样一个结构中，叶子一定是刚好10片，那么高度自然不会超过log10。

现在给出个[i,j]，要找这个区间里的最大值，怎么找呢？分情况讨论。如果i=1，j=10，那最好办，直接返回根节点储存的最大值就行了。如果运气没有这么好的话，那就得沿着根节点往下走了。先找出是在哪砍成两截分给两个儿子的，其实就是找中位数，然后看区间[i,j]跟中位数的关系。如果[i,j]全部都在左儿子里头，那就往左儿子里面找；如果全部都在右儿子，那就往右儿子找。最麻烦的，如果横跨了左儿子和右儿子，假定中位数分在了左儿子里面，那就从左儿子里找[i,中位数]的最大值，从右儿子里找(中位数,j]的最大值，然后取其中较大的那个就行了。

跳出这道题，其实线段树这种数据结构的优势主要是给离散的数据建模。比如POJ 2528 Mayor's posters，是将一个个不相交小的区间视为离散的点。更一般的，线段树体现的是data structure augmentation的methodology：往一种基础的数据结构加入新的信息，从而生成新的数据结构。从这个意义上来说，掌握线段树其实没啥意思，关键是自己要会灵活变通，根据自己的需要来构造不同的数据结构。