2013年09月11日

线段树之区间最大值


线段树

在大多数情况下,引入树的数据结构,可以将查找和插入的复杂度降低到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;
}
前一篇: Openstack Network学习(五) 后一篇: Linux逻辑卷的学习