用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法

RMQ(range minimum/maximum query)问题

给定一组数,给定给定一个区间,求区间最值,算法大致有以下几种

  1. O(n)算法,直接扫描一遍区间,求最值.
    优点:编程简单,可动态求解(数组可动态更改)
    缺点:不能处理大量数据.
  2. 使用线段树,可以优化成Log(N)
    优点:时间复杂度低,更改操作复杂度低
    缺点:编程复杂度大.
  3. 预处理O(N log N),查询O(1)的Sparse_Table(稀疏表)算法
    优点:编程简单,可动态求解(数组可动态更改)
    缺点:没啥,基本算法不能处理动态更改,改进后可以更改(复杂度貌似不小,大于LogN).
  4. 快速选择法 Quick Slect(打酱油的,不是RMQ),能在O(N) (我估算是1.5N)的时间内得到区间第K大/小值

下面主要介绍ST算法

Sparse_Table(稀疏表)算法

ST算法的区间分割
ST算法的区间分割

ST算法主要是应用了分治和动态规划的方法

将整个区间按如下方式分割

f[i][j]代表从i开始长度为\(2^{j}\)的一段区间(即\([i,i+2^{j}-1]\))中最大/小的值

例如:对于图中的区间[1,8],其最值为区间[1,4]和[5,8]中更优(最大或最小)的那一个

显然f[i][j]的值是\([i,i+2^{j}-1]\)的前一半(\([i,i+2^{j-1}-1]\))与后一半(\([i+2^{j-1},i+2^{j}-1]\))的最值中更优的那一个,这是一种分治策略,这便是为什么ST算法可以做到NlogN;



ST动画演示

可得出状态转移方程(以最大值为例):
\(f[i][j]=Max \left\{\begin{array}{ll}f[i][j-1]\\f[i+2^{j-1}][j-1]\end{array}\right.\)
显然,初值f[i][0]为弟i位的值;
递推方式:先递推j枚举区间长度,然后再枚举起始点,起始点+区间长度不能超过总区间长度
还用上图举例:

f[1][3]=Max{f[1][2],f[5][2]}
如右图,可以看到ST算法的分治策略,还可以看出基本ST算法是一个离线算法

关于动态修改维护

动态维护的方法是这样的

  1. 更新f[x][0]
  2. 枚举长度,j=1;2^j<=N;j++;
  3. 枚举起始点从以i为最后一个元素的区间到以x为初始点的区间

代码是下面折叠的那个

ST查询
ST算法查询
ST算法O(1)查询

找到两个长为\(2^{k}\)区间,区间长度的一半≤长度≤区间长度
\(\frac{{e – b}}{2} \le 2^k \le e – b + 1\) (b是要查询的区间的起点,e是要查询的区间的终点)
这两个区间能完全且的覆盖目标区间且不多覆盖,易证这两个区间最值的最值即为所求最值
理想的区间长度为\(log {}_2(e – b)\)

下面看代码:
输入格式:
N:区间长度
N个数:代表元素
M:查询个数
M个数对f,t,表明区间范围[f,t]
样例:

稍加修改可以去TYVJ 1038测试

动态代码,M个请求有变,c,a,b;c=1代表将第a位改为b,a=0代表查询[a,b];
样例:

动态RMQ代码

二维ST 算法

f[x][y][i][j]表示从点(x,y)开始x轴长为\(2^{i}\),y轴长为\(2^{j}\)的一个矩形

如图所示:

二维ST算法

其动规转移方程为

\(f[x][y][i][j] = \left\{ {\begin{array}{ll}{\max \left\{ {\begin{array}{ll}{f[x][y][i][j – 1]} \\{f[x][y + 2^{j – 1} ][i][j – 1]} \\\end{array}} \right.} & i=0\\{\max \left\{ \begin{array}{ll}f[x][y][i – 1][j] \\f[x + 2^{i – 1} ][y]i – 1][j] \\\end{array} \right.} & i\ne 0 \\\end{array}} \right.\)

解释:
每次DP,若是单行(i=0),则按一维方式DP
若不是,将目标区域分割为上下两部分(黄,绿),取其最值即可
我自己想的DP和大部分人的不一样,DP时将目标区域十字均分为4份求最值(和下面的查询差不多)而且代码长,效率可能也低,贴在后面。
查询时,将目标区域十字平分为4份,取其最值
帖代码:

我的Build函数,一开始要先一维DP f[x][y][i][0]和f[x][y][0][j],貌似不咋好,献丑

小给一组自创测试数据,挺强的。
格式:
行数,列数()
矩阵
请求次数M
M行,X1,X2,Y1,Y2

注意,”>?” 是C++中较大值运算符,结果为符号左右较大的那个。

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法

3 Responses

发表评论