RMQ算法总结
2023-12-16 04:51:56
知识概览?
- RMQ又叫ST表、跳表,可以用来解决区间最值问题,这里这有查询没有修改。当然,这样的问题用线段树也是可以解决的。
- RMQ算法本质上是倍增动态规划,它的思想是先倍增预处理再查询。f(i, j)表示从i开始,长度是的区间中,最大值是多少。递推公式是
? ? ? ??
例题展示
题目链接
活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/description/1275/
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 200010, M = 18;
int n, m;
int w[N];
int f[N][M];
void init()
{
for (int j = 0; j < M; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
if (!j) f[i][j] = w[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
init();
scanf("%d", &m);
while (m--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}
return 0;
}
参考资料?
- AcWing算法提高课
文章来源:https://blog.csdn.net/u012181348/article/details/135026961
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!