在大多数情况下，引入树的数据结构，可以将查找和插入的复杂度降低到O(logN)，树的结构设计也存在很多种，线段树就是其中一种，可以很方便的进行所谓的区间操作，例如，给定数组A[a1,a2,a3,……,an],查找某个区间[i,j]之间的最大值。
网上已经有很多的线段树的资料了，关于它的基本概念和使用例子，可以先参考下面两个链接：
这两篇博文都是大神总结出来的，详细，清晰易懂，感谢大神们的分享。
在我实际操作的过程中，感觉在写线段树时需要注意以下几点：
1.清楚在每一个节点中存储什么样的数据，例如对于求覆盖问题，则存储一个标记位，表示该区间是否已经覆盖。对于求区间最大值，那么存储该区间的最大值。灵活的设计节点存储的信息，可以解决不同的问题。 2.对于区间的划分，到底是以[ai,aj][aj,ak]还是[ai,aj][aj+1,ak]这样的方式来表示，需要根据具体的情况来看，同样例如求覆盖问题，需要使用前者，对于求最大值，可以使用后者。 3.线段树叶子节点表示的区间也需要仔细考虑，可以是[ai,ai]也可以是[ai,ai+1]等形式，这同样与想解答的问题相关。 4.对于上面的不同情况，需要考虑到大概需要申请多大的空间来存储线段树的所有节点。未经压缩的空间大小在2N左右。对于空间的压缩可以参考杨戈的讲稿 5.对于信息的更新，维护，查询，一定考考虑清楚，最高效率的利用好线段树的特征。
采取线段树来解决问题，那么需要先构建线段树，然后将数据插入到线段树中去，再插入的过程更新节点的信息，最后一步就是查找我们想要的结果。
对于前面提出的问题，如何查找区间的最大值了，那么我们可以在每个节点上存储该区间的最大值，然后就可以方便的查找了。
#include<iostream>
#include<iterator>
using namespace std;
typedef struct segtree{
int start;
int end;
int maxvalue;
}SegTree;
void construct(SegTree* segtree, int index,int left, int right){
if(segtree == NULL)
return;
segtree[index].start = left;
segtree[index].end = right;
if(right == left){
segtree[index].maxvalue = 0;
return;
}
int middle = (left + right) >> 1;
construct(segtree,(index<<1)+1,left,middle);
construct(segtree,(index<<1)+2,middle+1,right);
segtree[index].maxvalue = 0;
}
void insert(SegTree *segtree, int index,int num,int value){
if(segtree == NULL)
return;
if(num <= segtree[index].end && num >= segtree[index].start){
//cout << "value:" << value << " segtree:" << segtree[value].maxvalue << endl;
if(value > segtree[index].maxvalue)
segtree[index].maxvalue = value;
int middle = (segtree[index].start + segtree[index].end) >> 1;
if(num <= middle){
insert(segtree,(index<<1)+1,num,value);
}else{
insert(segtree,(index<<1)+2,num,value);
}
}
}
void insert(SegTree *segtree, int index,int value){
if(segtree == NULL)
return;
if(value <= segtree[index].end && value >= segtree[index].start){
if(value > segtree[index].maxvalue)
segtree[index].maxvalue = value;
int middle = (segtree[index].start + segtree[index].end) >> 1;
if(value <= middle){
insert(segtree,(index<<1)+1,value);
}else{
insert(segtree,(index<<1)+2,value);
}
}
}
int max(int a, int b){
return a > b ? a : b;
}
int getmaxvalue(SegTree *segtree,int index, int left, int right){
if(segtree == NULL){
return 0;
}
if(segtree[index].start >= left && segtree[index].end <= right){
return segtree[index].maxvalue;
}
if(segtree[index].start == segtree[index].end){
return segtree[index].maxvalue;
}
int middle = (segtree[index].start + segtree[index].end) >> 1;
if(left > middle){
return getmaxvalue(segtree,(index<<1)+2,left,right);
}else if(right <= middle){
return getmaxvalue(segtree,(index<<1)+1,left,right);
}
return max(getmaxvalue(segtree,(index<<1)+1,left,middle),getmaxvalue(segtree,(index<<1)+2,middle+1,right));
}
void print(SegTree *segtree, int len){
int i = 0;
for(i; i < len; i++){
cout << "index:" << i << " left:" << segtree[i].start << " right:" << segtree[i].end
<< " value:" << segtree[i].maxvalue << endl;
}
}
void testsegmenttree(){
int array[] = {3,4,1,9,10,32,18,6,7};
int len = sizeof(array) / sizeof(int);
copy(array,array+len,ostream_iterator<int,char>(cout," "));
cout << endl;
SegTree segtree[200];
construct(segtree,0,0,40);
int i = 0;
for(i; i < len; i++){
insert(segtree,0,i,array[i]);
}
//print(segtree,63);
int left;
int right;
while(cin >> left >> right){
cout << "left:" << left << " right:" << right << endl;
cout << "max value:" << getmaxvalue(segtree,0,left,right) << endl;
}
}
int main(){
testsegmenttree();
return 0;
}