RMQ 线段树中的错误

Question

我正在尝试构建用于执行 RMQ 的线段树。不知何故，无论我查询什么范围，它都会 return me 0.

比如我的数组是[ 1,2,3,4,5,6,7,8,9,10 ]。从索引 3 到 5 的 RMQ 应该给出 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));

因为我只是在查询，不应该修改树。

Answer 1

这行代码：

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

RMQ 线段树中的错误

Bug in RMQ Segment Tree

c++

algorithm

segment-tree

rmq