RMQ问题 及st表
rmq问题是多次询问闭区间内的最值,时间复杂度达到O(nlogn+m)
st表是一种不支持在线修改算法,专门解决rmq
下面是st表的详情
st[i][j]表示在i - ((2^j)-1)这个区间之内的最值
st[i][0]就等于a[i],不用说了
既然这样,那么怎么求出st的其他值呢?
st表O(nlogn)的预处理其实像极了LCA的初始化
因此st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
怎么样,是不是极为相似
那如果要查找怎么办呢,要查找的区间可不满足刚好是2的若干次方哦?
大家应该都知道,st表的单次查询时间是O(1),所以我们要用常数的查询方法(这不是废话吗,其实这就是废话)
先设t为log(y-x+1),也就是2^t<=(y-x+1) && 2^(t+1)>(y-x+1)
那么就可用min(st[x][t],st[y-(1<
给一个例题吧
洛谷P1816 忠诚
题目描述 老管家是一个聪明能干的人。他为财主工作了整整10年,财主为了让自已账目更加清楚。要求管家每天记k次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每次的账目按1,2,3…编号,然后不定时的问管家问题,问题是这样的:在a到b号账中最少的一笔是多少?为了让管家没时间作假他总是一次问多个问题。
输入输出格式 输入格式:
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题,n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式:
输出文件中为每个问题的答案。具体查看样例。
输入输出样例 输入
10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10
输出
2 3 1
题解:
闭区间多次求最值(rmq)
代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
【RMQ问题 及st表】以上就是rmq算法,我觉得画图似乎没有什么必要,谢谢大家的支持
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- JS中的各种宽高度定义及其应用
- jhipster|jhipster 升级无效问题
- 参保人员因患病来不及到指定的医疗机构就医,能否报销医疗费用()
- MybatisPlus|MybatisPlus LambdaQueryWrapper使用int默认值的坑及解决
- “精神病患者”的角度问题
- 解决SpringBoot引用别的模块无法注入的问题
- Hive常见问题汇总
- 姚老师互动问答会|姚老师互动问答会 # 问题001(如何更有智慧的和身边人分享金刚智慧())
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题