今天困得不行，就看了个小算法st，其实和线段树的作用一样，
不过这个算法没有用到数据结构，使用二进制优化的
是O(log(n)n)的时间预处理，然后以O(1)的时间返回（l,r)上的最大或最小
#include <iostream> #include <cmath> #include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long ll; const int N =1e5 +10; int a[N]; int n,m; int f[N][100]; void st_prework() { for(int i=1;i<=n;i++)f[i][0]=a[i]; int t = log(n)/log(2); for(int j=1;j<=t;j++) { for(int i=1;i<=n-(1<<j)+1;i++) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } int main() { cin >> n >> m; for(int i=1 ;i<=n;i++) { scanf("%d",&a[i]); } st_prework(); while(m--) { int l,r; scanf("%d%d",&l,&r); int k=log(r-l+1)/log(2); printf("%d\n", max(f[l][k],f[r-(1<<k)+1][k])); } return 0; }
st的题目：
#include <iostream> #include <cmath> #include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long ll; const int N =1e5 +10; int a[N]; int n,m; int f[N][100],d[N][100]; void st_prework() { for(int i=1;i<=n;i++)f[i][0]=a[i],d[i][0]=a[i]; int t = log(n)/log(2); for(int j=1;j<=t;j++) { for(int i=1;i<=n-(1<<j)+1;i++) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } } } int main() { cin >> n >> m; for(int i=1 ;i<=n;i++) { scanf("%d",&a[i]); } st_prework(); while(m--) { int l,r; scanf("%d%d",&l,&r); int k=log(r-l+1)/log(2); printf("%d\n", max(f[l][k] ,f[r-(1<<k)+1][k]) - min(d[l][k],d[r - (1<<k)+1][k])); } return 0; }
#include <iostream> #include <cmath> #include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long ll; const int N =1e5 +10; int a[N]; int n,m; int f[N][100],d[N][100]; void st_prework() { for(int i=1;i<=n;i++)f[i][0]=a[i],d[i][0]=a[i]; int t = log(n)/log(2); for(int j=1;j<=t;j++) { for(int i=1;i<=n-(1<<j)+1;i++) { d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } } } int main() { cin >> n >> m; for(int i=1 ;i<=n;i++) { scanf("%d",&a[i]); } st_prework(); for(int i=1;i<=n-m+1;i++) { int k =log(m)/log(2); printf("%d\n",min(d[i][k],d[i+m-1 - (1<<k)+1][k])); } return 0; }
原文：https://www.cnblogs.com/wangzhe52xia/p/11428600.html