http://blog.163.com/zhaohai_1988/blog/static/209510085201271112855692/
一般能用树状数组解决的问题，都可以用线段树解决。但是能用线段树解决的问题，树状数组不一定能解决。可能有人会有疑问，那你为什么还要写树状数组啊，因为树状数组实现起来比线段树简单百倍，非常容易掌握。
http://download.csdn.net/source/2255479
（2） 林涛文章《线段树的应用》：
http://wenku.baidu.com/view/d65cf31fb7360b4c2e3f64ac.html
（3） 朱全民文章《线段树及其应用》：
http://wenku.baidu.com/view/437ad3bec77da26925c5b0ba.html
（4） 线段树：
http://wenku.baidu.com/view/32652a2d7375a417866f8f51.html
假设要构造一个表示N个区间大小的线段树，线段树的根节点表示区间[0,N-1]，然后将区间分成两半，分别为左右子树表示，这样的线段树的节点只有2N-1个，是O(N)级别的，如图所示表示构造区间[1-5]的线段树。
线段树支持的操作有：构造，插入，查找，更新，删除；这些操作不一定都有，在实现上也不一定都是一个套路，这都取决于实际问题；实际上，通过在线段树节点上记录不同的信息，线段树可以完成很多不同的任务；线段树的高度为logn，这也就使得线段树可以在O(lgn)的时间完成插入、查询、删除等操作。
应用举例
在处理区间最值问题上，除了动态规划，线段树对于解决数列的区间问题也有着很大的优势，适用于和区间统计有关的问题。例如对某些数据可以按区间划分、按区间动态修改、按区间进行频繁查询，那么使用线段树可以达到较快的查询速度。
例如：给一个数的数列[A1，A2，… An]，并且可能多次进行如下操作：
1） 对序列中的某个数进行加减
2） 询问该序列任意一个子区间[i，j]的和是多少
显然，线段树可以在O(lgn)的时间完成这些操作，每个区间对应的节点增加一个记录区间和的信息即可，然后：
1） 操作一：因为序列里面Ai最多只会被线段树的logn个节点覆盖。只要求对线段树覆盖Ai的节点的区间和sum进行加减操作即可。
2） 操作二：只需找到区间所覆盖的区域，然后将区域和累加即可
这里引用《线段树与树状数组》（见参考资料）中的一句话，我觉得作者说的非常好：
用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。
先建树，然后插入数据，然后更新，查询。