线段树，也叫区间树，是一个完全二叉树，它在各个节点保存一条线段（即“子数组”），因而常用于解决数列维护问题，基本能保证每个操作的复杂度为o(lgn)。
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为n，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为o(logn）。而未优化的空间复杂度为2n，因此有时需要离散化让空间压缩。
线段树的基本操作主要包括构造线段树，区间查询和区间修改。
（1）线段树构造
首先介绍构造线段树的方法：让根节点表示区间[0,n-1]，即所有n个数所组成的一个区间，然后，把区间分成两半，分别由左右子树表示。不难证明，这样的线段树的节点数只有2n-1个，是o(n)级别的，如图：
节点定义如下：
完整的建树代码如下:
当在a[i]~a[j]上的所有的元素都加上一个值c的时候
如果a[i]~a[j]刚还是一个完整段的时候，直接将这个段的value值加上c*(r-l+1)
当更新的区间不是一个完整段的时候，采用一种记录增量的方法：给每个节点增加一个域：int add，记录更新操作的增量c，初始的时候add均为0，比如当对2~5区间更新后，给该结点的add加上一个值c，再下次要对2~3结点进行更新或查询时，再将add传递到下面的孩子结点中去
完整的更新树代码如下:
查询区间l~r上的value值
<a href="http://poj.org/problem?id=2182" target="_blank">poj2182 lost cows</a>
