9.1 RMQ问题
RMQ(Range Minimum/Maximum Query)问题,就是对于给定数组,在其下标范围[i, j]内给出的最小值(或最大值,下文都称最小值)的问题。
RMQ和LCA问题可以互相转化,一个对RMQ和LCA问题的总结如下表[i]:
算法
|
处理方式
|
复杂度
|
备注
|
转化算法
|
LCA =>±1RMQ
|
N/A
|
O(n)
|
引理1,规模O(n) - O(2n-1)
|
RMQ => LCA-CT
|
N/A
|
O(n)
|
引理2,规模不变
|
朴素算法
|
LCA-Naive
|
online
|
O(n^2) - O(1)
|
动态规划
|
RMQ-Naive
|
online
|
O(n^2) - O(1)
|
直接求解
|
经典算法
|
LCA-Tarjan
|
offline
|
O(na(n))
|
|
RMQ-ST
|
online
|
O(nlogn) - O(1)
|
|
改进算法
|
RMQ-ST-Block
|
online
|
O(nloglogn) - O(1)
|
将RMQ-ST分段处理
|
±1RMQ-ST-Block
|
online
|
O(n) - O(1)
|
控制RMQ-ST-Block中分段的段种数,得到O(n)算法。
|
快速算法
|
RMQ-Fast
|
online
|
O(n) - O(1)
|
RMQ => LCA-CT => ±1RMQ
|
折衷算法
|
RMQ-IT
|
online
|
O(n) - O(logn)
|
线段树直接处理
|
RMQ-CT-Tarjan
|
offline
|
O(na(n))
|
RMQ => LCA-CT再用LCA-Tarjan解决。
|
我们可以将一般RMQ的值得应用的算法列表:
算法
|
处理方式
|
复杂度
|
备注
|
RMQ-IT
|
online
|
O(n)-O(logn)
|
询问不多时,竞赛首选。
|
RMQ-CT-Tarjan
|
offline
|
O(na(n))
|
由于是离线的,而且还要转化成CT,某些地方不应用。
|
RMQ-ST
|
online
|
O(nlogn)-O(1)
|
询问多时,竞赛首选。
|
RMQ-ST-Block
|
online
|
O(nloglogn)-O(1)
|
时间要求特别严格时采用。
|
1.2 Sparse Table算法
RMQ的一个经典的算法是SparseTable(ST)算法。它可以在O(nlgn)的预处理时间后,提供O(1)时间的查询。
定义d[i, j]为下标在区间[i, i+2^j-1]中的数组S的元素的最小值。即:
d[i, j] = min{S[k] | i ≤ k ≤ i+2^j-1}
有:
d[i, j-1] = min{S[k] | i ≤ k ≤ i+2^(j-1)-1}
d[i+2^(j-1), j-1] = min{S[k] | i+2^(j-1) ≤ k ≤ i+2^(j-1)+2^(j-1)-1} =min{S[k] | i+2^(j-1) ≤ k ≤ i+2^j-1}
故此有:
d[i, j] = min{S[k] | i ≤ k ≤ i+2^j-1} = min{d[i, j-1], d[i+2^(j-1),j-1]}
可以观察到区间[i, i+2^j-1]被分为区间[i, i+2^(j-1)-1]和区间[i+2^(j-1), i+2^j-1]。
对于所有{(i, j) | 0 ≤ i ≤ n-1, 0 ≤i+2^j-1 ≤ n-1 }都求出d[i, j]。首先依据定义有d[i, 0] = S[i]。又由于有上述的递推式,所以在已求出d[i, j-1]和d[i+2^(j-1), j-1]的前提下,d[i, j]可以在常数时间内求出。又由于{(i, j) | 0 ≤ i ≤ n-1,0 ≤ i+2^j-1 ≤ n-1} = {(i, j) | 0 ≤ i ≤ n-1-(2^j-1), 0 ≤ 2^j-1 ≤ n-1},所以可以在[0, n-1]区间内遍历2^j-1,并对每个j,求出每个合要求的i对应的d[i,
j]。如果采用这种方法,在求解d[i, j]之前,d[i, j-1]和d[i+2^(j-1), j-1]都已经求出,故此求d[i, j]可以在常数时间内完成。由于j有O(lgn)个选择,而对每个j,i有O(n)个选择,故此求出数组d需要的时间是O(n lgn)。
假设要在[i, j]区间内查询最小值,即RMQ(i, j),则令k = max{l | 2^l ≤ (i-j+1)},即k为log(i-j+1)取下限。由此2^k*2 ≥ i-j+2,即i+2^k-1 ≥ j-2^k+1,所以[i, j]可被子区间[i, i+2^k-1]和[j-2^k+1, j]覆盖。而两个区间内的最小值分别是d[i, k]和d[j-2^k+1, k]。所以RMQ(i, j) = min{d[i, k], d[j-2^k+1,k]}。所以任意的查询都可以在O(1)时间内完成。
1.2.1实例
PKU JudgeOnline, 3264, Balanced Lineup.
1.2.2问题描述
给出一组数据,求出一个坐标区间内的最大值和最小值的相差范围。
1.2.3输入
63
1
7
3
4
2
5
15
46
22
1.2.4输出
6
3
0
1.2.5分析
这是经典的RMQ问题,用线段树也可以做。
可以发现,可以将二维数组d的两维互换,这样可以提高访问速度。
1.2.6程序
本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article
[i] http://adn.cn/blog/article.asp?id=20
分享到:
相关推荐
线性结构- ST 表与 RMQ.rar
--RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --几种凸包算法 --半平面交算法 --旋转卡壳算法 数据结构...
rmq-docker-win docker build -t gsxsolutions/rmq:3.5.4 -f .\Dockerfile.3.5.4 . docker build -t gsxsolutions/rmq:3.7.4 -f .\Dockerfile.3.7.4 . docker build -t gsxsolutions/rmq:3.7.5 -f .\Dockerfile....
开源项目-glycerine-rmq.zip,An R package to embed Golang in R, and R in Go. Serves R functions over websockets.
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
http://ybt.ssoier.cn:8088 信息学奥赛一本通(提高篇)测试数据\第4部分 数据结构(提高篇)\第2章 RMQ问题 测试数据
2015-BLUEZ-RMQ BlueZ和RMQ之间的adapter,主要透过命令列。这个专案包括两个部分 (1)MessageExchangeAgent 有含两个api,MessageSender负责送讯息到rabbitmq server;MessageReceiver负责从rabbitmq server接收...
后缀数组倍增算法实现 + RMQ问题ST算法实现
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
这是关于ACM 相关的 RMQ问题 算法资料。
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
RMQ问题求解(ST): RMQ问题 RMQ(Range Minimum/Maximum Query)问题,是求区间最大值或最小值,即范围最值问题。暴力解法是对每个询问区间循环求解,设区间长度n nn,询问次数m mm,则复杂度是O ( n m ) O(nm)O...
1、 概述LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法
| rmq-service | RMQ服务接口实现、基础消息服务接口实现、消息管理子系统服务接口实现 | | rmq-schedule-api | 消息确认子系统、消息恢复子系统服务接口 | | rmq-schedule | 消息确认子系统,与上游业务系统确认...
算法合集之RMQ与LCA问题PPT学习教案.pptx
上海人民RMQ6 系列自动转换开关产品样本201512pdf,
ACM算法模板的PDF版本,方便大家打印与使用,所有模板均经过测试。 最短路: SPFA模板 Dijkstra模板 Floyd模板 图论--最短路--第K短路(IDA*)(IDA Star)模板 传递闭包: 传递闭包 欧拉与...
可以实现马拉车算法 RMQ算法 tarjan算法
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
O(n)实现RMQ的算法,一般RMQ问题 到 O(n)构造笛卡尔树 到 <O(n), O(1)>的求解±1 RMQ问题