RMQ(range minimum/maximum query)问题
给定一组数，给定给定一个区间，求区间最值，算法大致有以下几种
- O(n)算法,直接扫描一遍区间,求最值.
优点:编程简单,可动态求解(数组可动态更改)
缺点:不能处理大量数据. - 使用线段树,可以优化成Log(N)
优点:时间复杂度低,更改操作复杂度低
缺点:编程复杂度大. - 预处理O(N log N),查询O(1)的Sparse_Table(稀疏表)算法
优点:编程简单,可动态求解(数组可动态更改)
缺点:没啥,基本算法不能处理动态更改，改进后可以更改(复杂度貌似不小，大于LogN). - 快速选择法 Quick Slect(打酱油的,不是RMQ)，能在O(N) (我估算是1.5N)的时间内得到区间第K大/小值
下面主要介绍ST算法
Sparse_Table(稀疏表)算法
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;
可得出状态转移方程(以最大值为例):
\(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算法是一个离线算法
关于动态修改维护
动态维护的方法是这样的
- 更新f[x][0]
- 枚举长度，j=1;2^j<=N;j++;
- 枚举起始点从以i为最后一个元素的区间到以x为初始点的区间
代码是下面折叠的那个
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]
样例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
input: 9 1 2 3 5 6 4 8 9 2 5 1 9 1 8 1 4 3 5 4 7 output: 9 9 5 6 8 |
稍加修改可以去TYVJ 1038测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <math.h> #include <stdlib.h> using namespace std; int f[1000][12];//动规数组 int N,M; inline void build();//预处理ST算法数组 inline int get(int b,int e); int main(){ int i,b,e; cin >> N; for (i=1;i<=N;i++) cin >> f[i][0]; build(); /* //打印动规数组 int j; for (i=1;i<=N;i++){ for (j=0;j<=(int)log2(N);j++) printf("%4d ",f[i][j]); cout << endl; } */ cin >> M; for (i=1;i<=M;i++) { cin >> b >> e; cout << get(b,e)<< endl; } system("pause"); } inline void build(){ int i,j, /*l=(int)log2(N)*/; for (j=1;(1<<j)<=N;j++)//区域大小(2^j)没必要超过整个区间 for (i=1;i+(1<<j)-1<=N;i++) f[i][j]=f[i][j-1] >? f[i+ (1<<(j-1)) ][j-1]; } inline int get(int b,int e){ int j=(int)log2(e - b+1);//区域长度的j,使得(2^j)大于等于请求区间的一半即可 return f[b][j] >? f[e-(1<<j)+1][j];//f[e-(1<<j)+1][j] 表示以e为中点长为2^j的区间 } |
动态代码，M个请求有变，c,a,b;c=1代表将第a位改为b，a=0代表查询[a,b];
样例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
input: 9 1 2 3 5 6 4 8 9 2 10 0 1 9 1 1 8 0 1 4 1 3 5 1 4 7 0 1 5 1 5 10 0 1 5 1 3 12 0 2 4 output: 9 8 8 10 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> #include <math.h> #include <stdlib.h> using namespace std; int f[1000][12];//动规数组 int N,M; //N:区间大小，M:数据个数 inline void build();//预处理ST算法数组 inline int get(int b,int e);//取得最大值 inline void set(int x,int y);//将y放置在x处并更新 int main(){ int i,b,e,p; cin >> N ; for (i=1;i<=N;i++) cin >> f[i][0]; build(); /* //打印动规数组 int j; for (i=1;i<=N;i++){ for (j=0;j<=(int)log2(N);j++) printf("%4d ",f[i][j]); cout << endl; } */ cin >> M; int c; for (i=1;i<=M;i++) { cin >> c; if (c==1){//修改 cin >> b >> p; set(b,p); } else {//查询 cin >> b >> e; cout << get(b,e)<< endl; } } system("pause"); } inline void build(){ int i,j, /*l=(int)log2(N)*/; for (j=1;(1<<j)<=N;j++)//区域大小(2^j)没必要超过整个区间 for (i=1;i+(1<<j)-1<=N;i++) f[i][j]=f[i][j-1] >? f[i+ (1<<(j-1)) ][j-1]; } inline int get(int b,int e){ int j=(int)log2(e - b+1);//区域长度的j,使得(2^j)大于等于请求区间的一半即可 return f[b][j] >? f[e-(1<<j)+1][j];//f[e-(1<<j)+1][j] 表示以e为中点长为2^j的区间 } inline void set(int x,int y){//将y放置在x处并更新 int i,j; f[x][0]=y; for (j=1;(1<<j)<=N;j++) for (i=x-(1<<j)+1 >? 1;i<=x && i+(1<<j)-1<=N;i++ ) //应从最早包含x位的一位开始循环，即x-(1<<j)+1，但有可能为负数 f[i][j]=f[i][j-1] >? f[i+ (1<<(j-1)) ][j-1]; } |
二维ST 算法
f[x][y][i][j]表示从点(x,y)开始x轴长为\(2^{i}\),y轴长为\(2^{j}\)的一个矩形
如图所示：
其动规转移方程为
\(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份，取其最值
帖代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <math.h> #include <stdlib.h> #define max(x,y) (x)>(y)?(x):(y) using namespace std; int f[300][300][11][11];//x,y,高，宽 int R,C,M; inline void build(); inline void build2();//Comzyh写的 inline int get (int x1,int y1,int x2,int y2); int main(){ int i,j; cin >> R >> C; for (i=1;i<=R;i++) for (j=1;j<=C;j++) cin >> f[i][j][0][0]; build(); cout << "Please enter M ..." << endl; cin >> M; int x1,y1,x2,y2; for (i=1;i<=M;i++){ cin >> x1 >> y1 >> x2 >> y2; cout << get (x1,y1,x2,y2) << endl; } system("pause"); }s inline void build (){ int i,j,x,y; for (i=0;(1<<i)<=R;i++)//循环高度 for (j=0;(1<<j)<=C;j++)//循环宽度 if (i!=0 || j !=0) for (x=1;x+(1<<i)-1<=R;x++)//循环纵坐标 for (y=1;y+(1<<j)-1<=C;y++)//循环横坐标 if (i==0) f[x][y][i][j] = f[x][y ][i][j-1] >? f[x][y+(1<<j-1)][i][j-1]; else f[x][y][i][j] = f[x ][y][i-1][j] >? f[x+(1<<i-1)][y][i-1][j]; } inline int get (int x1,int y1,int x2,int y2){ int lx= (int)log2(x2 - x1 + 1), ly= (int)log2(y2 - y1 + 1); return ( f[x1 ][y1 ][lx][ly] >? f[x1 ][y2 - (1<<ly)+1][lx][ly])>? ( f[x2-(1<<lx)+1][y1 ][lx][ly] >? f[x2-(1<<lx)+1][y2 - (1<<ly)+1][lx][ly]); } |
我的Build函数,一开始要先一维DP f[x][y][i][0]和f[x][y][0][j],貌似不咋好,献丑
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
inline void build2(){//Comzyh的初始化，效率不高 ，献丑 int i,j,x,y; //初始化f[x][y][0][j]; for (j=1;(1<<j)<=C;j++)//循环宽度z for (x=1;x<=R;x++)//循环纵坐标 for (y=1;y+(1<<j)-1<=C;y++)//循环横坐标 f[x][y][0][j]=f[x][y][0][j-1] >? f[x][y+(1<<(j-1))][0][j-1]; //初始化f[x][y][i][0]; for (i=1;(1<<i)<=R;i++)//循环高度 for (x=1;x+(1<<i)-1<=R;x++)//循环纵坐标 for (y=1;y<=C;y++)//循环横坐标 f[x][y][i][0]=f[x][y][i-1][0] >? f[x+(1<<(i-1))][y][i-1][0]; //DP for (i=1;(1<<i)<=R;i++)//循环高度 for (j=1;(1<<j)<=C;j++)//循环宽度 if (i!=0 || j!=0) for (x=1;x+(1<<i)-1<=R;x++)//循环纵坐标 for (y=1;y+(1<<j)-1<=C;y++)//循环横坐标 f[x][y][i][j] = ( f[x ][y ][i-1][j-1] >? f[x+(1<<i-1)][y ][i-1][j-1])>? ( f[x ][y+(1<<j-1)][i-1][j-1] >? f[x+(1<<i-1)][y+(1<<j-1)][i-1][j-1] ); } |
小给一组自创测试数据,挺强的。
格式:
行数,列数()
矩阵
请求次数M
M行，X1,X2,Y1,Y2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Input： 10 10 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 1 6 4 23 8 41 25 41 3 4 5 4 85 1 2 1 5 1 32 2 4 52 1 5 5 2 3 1 5 5 0 0 0 0 0 0 0 0 0 0 1 63 1 3 14 5 10 0 0 1 5 6 1 9 1 0 1 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 1 10 10 1 9 10 10 1 1 5 2 6 6 10 10 9 9 10 10 6 5 8 7 答案就不给了 |
注意，”>?” 是C++中较大值运算符，结果为符号左右较大的那个。
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: 用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法
3q so much