转自：http://blog.csdn.net/x314542916/article/details/7837276
线段树(interval tree) 是把区间逐次二分得到的一树状结构，它反映了包括归并排序在内的很多分治算法的问题求解方式。
【声明】
1 #include<cstdio> 2 #include<cmath> 3 const int MAXNODE = 2097152; 4 const int MAX = 1000003; 5 struct NODE{ 6 int left,right; // 区间[left,right] 、 7 int value; // 节点区间对应的权值、 8 }node[MAXNODE]; 9 int father[MAX]; // 每个点(当区间长度为0时，对应一个点)对应的结构体数组下标
【创建线段树（初始化）】：
线段树是用二叉树结构存储的，而且是完全二叉树
在完全二叉树中假如一个结点的序号（数组下标）为 n ，那么 （二叉树基本关系）
n的父亲为 n/2，
n 的另一个兄弟为 n/2*2 或 n/2*2+1
n 的两个孩子为n*2 (左) n*2+1(右)
根据这样的关系，就可以很简单明了的写出建树的代码了
1 void buildtree(int i,int left,int right) // 为区间[left,right]建立一个以结点i为祖先的线段树，i又为为数组下标，也是结点序号 2 { 3 node[i].left=left; //写入第i个结点的 左区间 、 4 node[i].right=right; //写入第i个结点的 右区间 、 5 node[i].value=0; // 对每个区间进行初始化 、 6 if(left==right){ // 当区间长度为0的时候，结束递归、 7 father[left]=i; //能知道某个点对应的序号，为了更新的时候从下往上一直到顶，也就是保存left对应结点i在结构体数组中的位置 8 return; 9 } 10 // 该结点往 左孩子的方向 继续建立线段树 11 // 这里将 区间[left,right] 一分为二了 12 buildTree(i<<1, left, (right+left) / 2)); 13 // 该结点往 右孩子的方向 继续建立线段树 14 buildTree((i<<1)+1, (right+left) / 2 + 1, right); 15 }
【单点更新线段树】：
最初用father数组保存了每一个单位区间长度的结点下标，因此就容易由下往上更新了
（此处以更新区间最大值为例）
1 void updatatree(int ri) //从下往上更新（这个点本身已经在函数外面更新过了） 2 { 3 if(ri==1) return; // 已经找到整个树的根节点了，结束递归 4 int fi = ri / 2; // ri的父结点 5 //该父结点的两个孩子 6 int a = node[fi<<1].value; 7 int b = node[(fi<<1)+1].value; 8 node[fi].value=(a>b)?(a):(b); //更新这个父结点 9 updatatree(ri/2); // 继续递归，由父结点往上找 10 }
【查询区间最大值】：
将一段区间按照建立的线段树从上往下一直拆开，直到存在有完全重合的区间停止。对照图例建立的树，假如查询区间为 [2,5] 
红色的区间为完全重合的区间，因为在这个具体问题中我们只需要比较这 三个区间的值 找出 最大值 即可。
1 int Max = -1 << 20; 2 void query(int i,int l,int r) 3 { 4 if(node[i].left==l && node[i].right==r){ // 找到一个完全重合区间 5 Max = (Max < node[i].value)?node[i].value:(Max); 6 return; 7 } 8 i = i << 1; //查找此结点的左孩子结点 9 if(l <= node[i].right){ // 左区间有涉及 10 if(r<=node[i].right) // 全包含于左区间，则查询区间形态不变 11 query(i,l,r); 12 else // 半包含于左区间，则查询区间拆分，左端点不变右端点变为左孩子的右区间 13 query(i,l,node[i].right); 14 } 15 i+=1; //右孩子结点 16 if(r >= node[i].left){ //右区间有涉及 17 if(l >= node[i].left) //全包含于右区间，查询状态不变 18 query(i,l,r); 19 else // 半包含于左区间，查询区间拆分 20 query(i,node[i].left,r); 21 } 22 }