关于ST表:
ST表是用来求RMQ问题的一种在线算法. 只能解决多次询问, 没有修改的情况. 初始化复杂度O(nlogn), 查询O(1).
ST表用了dp和倍增的思想: dp解决了每个位置往后1,2,4,8,16....长度的最大值是多少, 倍增解决了"已知每个位置往后1,2,4,8,16....长度的最大值, 得到任意区间最大值"的问题.我们具体来看:
maxx[i][j]表示i为起点长度为j^2的区间最大值. 观察可发现:
i起点2^j长度的区间最大值=max( i起点2^(j-1)长度的区间最大值, i+2^(j-1)为起点长度为2^(j-1)的区间最大值 ).
设k=floor(log(r-l+1)), 则l到r的区间最大值为max(maxx[l][k],maxx[r-2^k+1][k]), 当k不恰好等于log(len)时, 两个区间就会重叠, 但时重叠并不影响求最值鸭.
ST表参考 log求法参考 倍增思想 树上倍增
这个模板题, 求区间最大最小差值. 数组1e5,查询1e6
代码:
//#include<bits/stdc++.h> #include<algorithm> #include<cstdio> #define fuck(x) std::cout<<"["<<#x<<"->"<<x<<"]"<<endl; using namespace std; typedef long long ll; const int M=5e4+5; int n,q; int a[M]; int maxx[M][33];//从i开始,长度是2^j的区间内最大值 int minn[M][33]; int log2(int x) {//迭代求log2(x) int k=0,y=2; while(y<=x) { k++; y<<=1; } return k; } int main() { scanf("%d%d",&n,&q); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); maxx[i][0]=minn[i][0]=a[i]; } for(int j=1; j<=31; j++) {//先枚举完长度为1的 for(int i=1; i<=n; i++) { if(i+(1<<j)-1>n) continue; maxx[i][j]=max(maxx[i][j-1], maxx[i+( 1<<(j-1) )][j-1] ); minn[i][j]=min(minn[i][j-1], minn[i+( 1<<(j-1) )][j-1] ); } } for(int i=0; i<q; i++) { int l,r; scanf("%d%d",&l,&r); int k=log2(r-l+1); printf("%d\n",max(maxx[l][k],maxx[r-(1<<k)+1][k]) -min(minn[l][k],minn[r-(1<<k)+1][k])); } return 0; }
