基于简单线段树的RMQ

线段树是擅长处理区间的，是一种类似完美二叉树的数组结构。(完美二叉树是所有叶子深度都相同，并且每个节点要么是叶子节点要么有两个儿子的树)。树上的每个节点都维护一个区间。根维护都是整个区间，每个节点维护的是父亲的区间二等分后的其中一个子区间，对区间对操作可以在O(logn)完成。

基于简单线段树的RMQ

const int MAX_N = 1<<17;
int n,dat[2*MAX_N-1];

//初始化
void init(int n_){
    n = 1;
    while(n<n_){
        n*=2;
    }
//将所有对值都设置为INT_MAX
    for(int i=0;i<2*n-1;i++){
       dat[i] = INT_MAX; 
    }
}
//更新第k个元素为a(index 0-n)
void updata(int k,int a){
    k+=n-1;
    dat[k] = a;
    //更新上层元素
    while(k>0){
        k=(k-1)/2;
        dat[k] = min(data[2*k+1],dat[2*k+2]);
    }
}
//求[a,b]的最小值
//k是节点编号,ab是所求区间，lr是对应的(l,r)区间
void query(int a,int b,int k,int l,int r){
    //如果(a,b)不在(l,r)区间内(无交集)，返回INF_MAX
    if(a>=r || b<=l){
        return INF_MAX;
    }
    //如果(a,b)包含(l,r)，返回当前节点值
    if(a>=l&&b<=r){
        return dat[k];
    }
    //如果有交集，并且(a,b)不包含(l,r)，向下递归,返回两个子节点的最小值
    else{
        int vl = query(a,b,k*2+1,l,(l+r)/2);
        int vr = query(a,b,k*2+2,(l+r)/2,r);
        return min(vl,vr);
    }
}

线段树有几个规律:

1、完美二叉树形式的线段树的dat数组长度为 2*n-1;(2n=n+n/2+n/4+....)

2、如果我们要更新第k个元素(k从0开始)，则该元素在dat中的下标为k=n-1+k,即更新dat[n-1+k]，既然该元素更新了，那么上层也要更新，上层的下标为k=(k-1)/2,dat[k]=min(dat[k*2+1],dat[k*2+2]);(dat[k*2+1]该节点的左子树,dat[k*2+2]该节点的右子树)。

基于简单线段树的RMQ

相关推荐