RMQ ：用于求一个区间内的最大最小值
ST算法代码
时间复杂度：预处理O（n * log n） 查询O（1）
#include <stdio.h> #include <iostream> #include <string.h> #include <stack> #include <algorithm> #include <queue> #include <map> #include <cmath> #define eps 0.000001 #define pi acos(-1,0) #define pr 999983 #define LL long long using namespace std; int n,m; int _2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}; int a[10000][100]; void RMQ(){ int z=0; while (_2[z]<=n) z++; for (int i = 1; i < z; i++){ for (int j = 0; j <= n-_2[i]; j++){ a[j][i]=min(a[j][i-1],a[j+_2[i-1]][i-1]); } } } int main(){ while (~scanf("%d",&n)){ for (int i = 0; i < n; i++){ scanf("%d",&a[i][0]); } RMQ(); scanf("%d",&m); while (m--){ int l,r,x; scanf("%d%d",&l,&r); x=(int)(log(r-l+1)/log(2.0)); printf("%d\n",min(a[l][x],a[r-(1<<x)+1][x])); } } return 0; }
不知名大神代码
时间复杂度：预处理O（n * log n） 查询O（log n）
#include <stdio.h> #include <iostream> #include <string.h> #include <stack> #include <algorithm> #include <queue> #include <map> #include <cmath> #define eps 0.000001 #define pi acos(-1,0) #define pr 999983 #define LL long long using namespace std; int n,m; int _2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}; int a[10000][100]; int fd(int l,int x){ int z=0; while (_2[z]<=x) z++; z--; if (_2[z]<x) return min(a[l][z],fd(l+_2[z],x-_2[z])); return a[l][z]; } void RMQ(){ int z=0; while (_2[z]<=n) z++; for (int i = 1; i < z; i++){ for (int j = 0; j <= n-_2[i]; j++){ a[j][i]=min(a[j][i-1],a[j+_2[i-1]][i-1]); } } } int main(){ while (~scanf("%d",&n)){ for (int i = 0; i < n; i++){ scanf("%d",&a[i][0]); } RMQ(); scanf("%d",&m); while (m--){ int l,r,x; scanf("%d%d",&l,&r); x=r-l+1; printf("%d\n",fd(l-1,x)); } } return 0; }