基于线段树的RMQ

开发者玉淇技术 2022年11月15日

0 收藏 548 点赞 4,246 浏览 777 个字

RMQ（Range Minimum/Maximum Query）区间最值查询，即给出长度为n的数组A，以及m组询问s、t(s<=t<=n)，返回区间[s,t]中的最值。

基于线段树的方法实现的话，建树O(n)，查询O(logn)，相比ST，适合用于n更大，m较小的情况。

void built(int k, int l, int r)
{
    if (l==r) t[k] = a[l]; //到叶子上，则赋值
    else {
        built(k*2+1, l, (l+r)/2); //左儿子
        built(k*2+2, (l+r)/2, r); //右儿子
        t[k] = min(t[k*2+1], t[k*2+2]); //回溯赋值
    }
}
void update(int k, int a)
{
    //叶子节点
    k += n-1;
    t[k] = a;
    //向上更新
    while (k>0) {
        k = (k-1)/2;
        t[k] = min(t[k*2+1], t[k*2+2]);
    }
}
int query(int a, int b, int k, int l, int r) //查询区间[a,b], 当前查询结点的位置为k, 所表示的区间为[l,r],默认k为根结点
{
    if (r<=a||b<=l) return INF; //当前区间与所查询区间无交集，返回一个不影响答案的值
    if (a<=l&&r<=b) return t[k]; //当前区间包含于所查询区间，直接返回当前区间的最值就好了
    else {
        int vl = query(a, b, k*2+1, l, (l+r)/2); //查询左儿子
        int vr = query(a, b, k*2+1, (l+r)/2, r); //查询右儿子
        return min(vl, vr);
    }
}