RMQ段树中的错误

我正在尝试构建一个用于执行RMQ的段树。不知何故，无论我查询什么范围它将返回我0.RMQ段树中的错误

例如，我的数组是[ 1,2,3,4,5,6,7,8,9,10 ]。 RMQ从指数3到5应该给4.但我的代码保持输出0

我的代码：

#include<bits/stdc++.h> 

using namespace std; 

#define ll long long 

ll N, st[2*100000], arr[100000]; 

void build(int r, int lo,int hi) { 
    if(lo==hi) { 
     st[r] = arr[lo]; 
    } else { 
     build(r<<1,lo,(lo+hi)>>1); 
     build((r<<1)|1,((lo+hi)>>1)+1,hi); 
     st[r] = min(st[r<<1],st[(r<<1)|1]); 
    } 
} 

void update(int r,int lo,int hi,ll val,int i) { 
    if(lo==hi) { 
     st[r] = val; 
    } else { 
     int mid = (lo+hi)>>1; 
     if(lo <= i && i <= mid) { 
      update(r<<1,lo,mid,val,i); 
     } else { 
      update((r<<1)|1,mid+1,hi,val,i); 
     } 
     st[r] = min(st[r<<1],st[(r<<1)|1]); 
    } 
} 

ll query(int r,int lo,int hi,int a,int b) { 
    if(lo > b || hi < a) { 
     return LLONG_MAX; 
    } else if(lo <= a && hi >= b) { 
     return st[r]; 
    } else { 
     int mid = (lo+hi)>>1; 
     return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b)); 
    } 
} 

int main(void) { 
    for(int i = 0; i <= 10; i++) arr[i] = i; 
    build(1,0,10); 
    cout << query(1,0,10,3,5) << endl; 
    return 0; 
}

编辑：

感谢所有帮助。就像下面提到的答案一样，我的查询范围是错误的。还有2个错误除此之外：

if(lo <= a && hi >= b)应该(a <= lo && b >= hi)

和

return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

应该

return min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

，因为我只进行查询，并应不要修改树。

来源

2016-12-05 LanceHAOH

这行代码：

return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

为什么你改变你的短a和b你改变你的查询在每一个递归调用。应该

return st[r] = min(query(r<<1,lo,mid,a,b),query((r<<1)|1,mid+1,hi,a,b));

，也是你的更新功能是错误的：

Check Here

来源

2016-12-05 17:33:49 DreamWorks

RMQ段树中的错误

回答

相关问题