RMQ算法（计算机求区间最值算法）

于 2024-08-14 由 ciye 发布

一、求区间最大值的各种方法及时间复杂度
1、朴素（即搜索），O(n)-O(qn) online。
2、线段树，O(n)-O(qlogn) online。
3、ST（实质是动态规划），O(nlogn)-O(q) online。
ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k＜=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。
d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。
4、RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(q) online。
首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。

RMQ算法时间复杂度：
***时间复杂度为O(nlogn),然后可以在O(1)的时间内处理每次查询。***

二、RMQ模板题

> https://ac.nowcoder.com/acm/contest/88527/H
ac代码：`https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70974305`

三、RMQ模板
```

int n,a[1000005];
int dp[100005][25];
void rmq_init(){
    for(int i = 1; i <= n; i++)
        dp[i][0] = a[i];
    for(int j = 1; (1<<j) <= n; j++){
        for(int i = 1; i+(1<<j)-1 <= n; i++){
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
       	}
    }
}
int rmq(int l, int r){
    int k=0;
    while(1<<(k+1) < r-l+2)
        k++;
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}

```

四、参考资料
1.`https://blog.csdn.net/Struggle_0/article/details/109169076`
2.`https://blog.csdn.net/Struggle_0/article/details/109166581`

分类：算法
标签：无标签

Ciyeblog

RMQ算法（计算机求区间最值算法）

于 2024-08-14 由 ciye 发布

暂无评论

发表评论