RMQ算法
2021/7/31 17:07:41
本文主要是介绍RMQ算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
RMQ算法
RMQ(Range Minimun/Maximum Query),即区间查询最值,适用于需要多次查询区间最值的问题。RMQ需要 \(O(n\log n)\) 的预处理,之后可以在 \(O(1)\) 的时间内处理每次查询。
下面的演示我们以查询最小值为例。
获取ST表 \(O(nlogn)\)
RMQ算法采用倍增的思想,设 \(st[i][j]\) 表示区间 \([i, i + 2 ^ j - 1]\) 中的最值,即 \(i\) 后 \(2^j\) 个数字的最值。我们可以把区间分为两半 \([i,i+2^{j-1}-1]\) 和 \([i+2^{j-1},i+2^j-1]\),则最值可以表示为这两个子区间的最值,显然这两个区间最值为 \(st[i][j-1]\) 和 \(st[i+(1<<j-1))][j-1]\) 。则状态转移方程为:
\[st[i][j] = min(st[i][j-1], st[i+2^{j-1}][j-1]) \]我们把这个数组记为\(st\)表,于是我们得出代码:
Code
void RMQ () { for (int i = 1; i <= n; i++) st[i][0] = a[i]; // 边界处理 for (int j = 1; (1 << j) <= n; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) st[i][j] = min(st[i][j-1], st[i+(1<<j-1)][j-1]); }
注意,状态转移方程是从小区间转移到大区间,所以我们要先处理小区间。也就是范围要先循环。
如何查询\([l, r]的最值\) \(O(1)\)
由于\(st\)表是由倍增构建的,所以只能存储2的幂次方长度的区间最值,那么我们要怎么求任意区间的最值呢?
同样的,我们把区间分为两段,\([l,l+2^k-1]\) 和 \([r-2^k+1,r]\),这里k表示长度不超过\(r-l+1(查询区间的长度)\)的倍增区间的倍增幂指数。如下图:
显然,查询的区间最值只需要在这两个子区间中求出最值即可,即:
\[Minimum = min(st[i][k], st[r-2^k+1][r]); \qquad k = log2(r-l+1) \]Code
int query (int l, int r) { int k = log2(r-l+1); return min(st[i][k], st[r-(1<<k)+1][k]); }
这篇关于RMQ算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08「布道师系列文章」解析 AutoMQ 对象存储中的文件存储格式
- 2024-05-08「布道师系列文章」小红书黄章衡:AutoMQ Serverless 基石-秒级分区迁移
- 2024-05-08AutoMQ 系统测试体系揭秘
- 2024-03-14AutoMQ 携手阿里云共同发布新一代云原生 Kafka,帮助得物有效压缩 85% Kafka 云支出!
- 2024-02-22kafka partitioner
- 2024-01-24AutoMQ生态集成 - 将数据从 AutoMQ Kafka 导入 RisingWave 数据库
- 2024-01-13消息队列面试题:为什么要使用消息队列?
- 2024-01-08"基于 XHAMQ 的消息队列系统实现"
- 2023-11-24全网最全图解Kafka适用场景
- 2023-09-19RabbitMQ 消息应答