ftp空间网站,网站建设项目报告总结报告,湖南建设人才网官网,成立做网站的公司有哪些RMQ问题 ST 表 用状态 s[i][j] 记录区间长度为 2^j 的长度的区间的最大值
所以状态转移方程就是 st[i][j] max( st[i][j-1] , st[i(1 (j-1))][j-1] )
注意状态转移的方向#xff0c;保证区间合法性#xff08;i2^j 不能超过数组大小#xff09;
写完这些后 max( st[i][j-1] , st[i(1 (j-1))][j-1] )
注意状态转移的方向保证区间合法性i2^j 不能超过数组大小
写完这些后定义好第一个就可以从前往后进行计算
用ST表进行区间查询 ST表存储的区间是2的整数倍所以要计算的是如何从要求的区间到ST表存储的区域。
要寻找一个k如果满足以下的大小关系 就可以取两个区间的最大值 max(st[l][k],st[r-(1k)][k])这两个区间是囊括了整个要求的区域。 k值的具体计算是把(r-l1)对2求对数并向下取整可以用强制类型转换来实现。
求区间最大值的代码
#include iostream
#include algorithm
#include cmath
using namespace std;#define ll long longconst int N 5e5 5;
int n,q;
ll a[N];
ll st[N][21];ll getMax(int l,int r)
{//计算k区间长度对2取对数int k log(r-l1)/log(2);return max(st[l][k],st[r-(1k)1][k]);
}int main()
{// 请在此输入您的代码cin n q;for(int i 1 ; i n ; i){int x;cin x;a[i] x;}//构造ST表//1.初始化for(int i 1 ; i n ; i) st[i][0] a[i];//2.利用状态转移方程求ST表for(int j 1 ; j 20 ; j){for(int i 1 ; i n ; i){if(i (1j) -1 n) //不要忘记-1是要区间长度为 2^j 的{st[i][j] max(st[i][j-1],st[i(1(j-1))][j-1]);}}}//3.利用ST表来求区间最大值while(q--){int l,r;cin l r;cout getMax(l,r) \n;}return 0;
}
