网站建设和维护实训,珠海品牌网站制作,建设网站有何要求,Wordpress税表简介 ST表是利用倍增思想处理RMQ问题#xff08;区间最值问题#xff09;的一种工具。 它能够做到O(nlogn)预处理#xff0c;O(1)查询的时间复杂度#xff0c;效率相当不错。 算法 1.预处理 ST表利用倍增的思想。以洛谷的P3865作为例子。我们需要查询某一区间的最大值。 我…简介 ST表是利用倍增思想处理RMQ问题区间最值问题的一种工具。 它能够做到O(nlogn)预处理O(1)查询的时间复杂度效率相当不错。 算法 1.预处理 ST表利用倍增的思想。以洛谷的P3865作为例子。我们需要查询某一区间的最大值。 我们用f[ i ][ j ]表示区间i到i2^j-1的最大值最小值同理。在状态转移时我们可以把这个区间拆成两个区间分别求最大值。 因此状态转移方程为 f[i][j] max{ f[i][j-1], f[i2^(j-1)][j-1] } 2.查询 查询也比较简单。 我们先求出log2(区间长度),令其等于k。 然后我们对左右端点分别查询即图中的绿色线条和红色线条保证能够覆盖我们需要查询的整个区间。 为什么从右端点开始查询左端点为r-2^k1 其实很简单我们需要寻找一个x使得x2^k-1r。所以xr-2^k1。 上代码 //ST表求静态区间最大值 洛谷P3865
#include iostream
#include cstdio
#include cmathusing namespace std;const int maxn1e610;
int n,m;
int Max[maxn][21];//Max[i][j]表示区间i到i2^j-1的最大值int read()
{char chgetchar();int f1;int x0;while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}int find(int l,int r)
{int klog2(r-l1);//计算log2(区间长度)return max(Max[l][k],Max[r-(1k)1][k]);
}int main()
{nread();mread();for(int i1;in;i){Max[i][0]read();}for(int j1;j21;j){for(int i1;i(1j)-1n;i){Max[i][j]max(Max[i][j-1],Max[i(1(j-1))][j-1]);//倍增//1(j-1)表示2^(j-1)}}for(int i1;im;i){int lread();int rread();printf(%d\n,find(l,r));}return 0;
} 转载于:https://www.cnblogs.com/Bw-Orzzzzz/p/10829036.html
