RMQ 模板
2024-10-07 08:35:25
RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为
n的数列A,回答若干次询问RMQ(i,j),返回数列A中下标在区间[i,j]中的最小/大值。
这个有很多算法:这里介绍一种比较高效的ST算法解决这个问题。ST(Sparse Table)算法可以
在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。
令dp(i,j)表示从 i 开始的,长度为 2^j 的一段中元素的最小值,
即可以递推出dp(i,j)=min(dp(i,j-1),dp(i+2^(j-1) , j-1))。
代码:
void ST(int n) {
for (int i = ; i <= n; i++)
dp[i][] = A[i];
for (int j = ; ( << j) <= n; j++) {
for (int i = ; i + ( << j) - <= n; i++) {
dp[i][j] = max(dp[i][j - ], dp[i + ( << (j - ))][j - ]);
}
}
}
int RMQ(int l, int r) {
int k = ;
while (( << (k + )) <= r - l + ) k++;
return max(dp[l][k], dp[r - ( << k) + ][k]);//int k=(int)(log(double(R-L+1))/log(2.0));
}
转载来自:https://www.cnblogs.com/linhaitai/p/9703161.html
最新文章
- iOS索引列开发详解
- 如果你恨一个程序员,忽悠他去做iOS开发
- python操作memcached以及分布式
- dwz_bootstrap + thinkphp
- 把Linux安装到移动硬盘上
- 简单的Java Web服务器
- asp.net MVC webservice 报次错解决方法
- 数据结构(C语言版)---第三章栈和队列 3.4.2 队列的链式表示和实现(循环队列)
- Linux散列表(二)——宏
- python模拟登录知乎
- HDU1114--Piggy-Bank(完全背包变形)
- SSM 配合 Mysql 数据库和代码数据源主从分离
- PCI9054 DMA设置流程
- 【linux】工作时使用的命令
- cumsum函数
- Python: Ubuntu 安装numpy,scipy,matplotlib
- Extjs相关知识点梳理
- Scala隐式转换和隐式参数
- 【RL系列】蒙特卡罗方法——Soap Bubble
- nodejs返回接口给前端