概述：用倍增法求区间最值的离线算法，O(nlogn)预处理，O(1)访问。

预处理：

　　状态：st[i][j]：[i,i+2^j)之间的最值　　

　　状态转移：如果j等于0，st[i][j]=a[i]

　　　　　　　如果j大于0，st[i][j]=max(st[i][j-1],st[i+2^(j-1)][j-1])或st[i][j]=min(st[i][j-1],st[i+2^(j-1)][j-1])

访问：

　　求[l,r]区间里的最值

　　k=floor(log(r-l+1))

　　ans=max(st[l][k],st[r-2^k+1][k])或ans=min(st[l][k],st[r-2^k+1][k])

模板：

int st[N][20],a[N];void init_st(int n){    for(int i=n;i>=1;i--){        st[i][0]=a[i];        for(int j=1;i+(1<
     
      <=n;j++){            st[i][j]=min(st[i][j-1],st[i+(1<
     

 例题：

思路：求区间最值差

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int ss[N][20],st[N][20],a[N];void init_st(int n){    for(int i=n;i>=1;i--){        st[i][0]=a[i];        ss[i][0]=a[i];        for(int j=1;i+(1<
           
            <=n;j++){ st[i][j]=min(st[i][j-1],st[i+(1<
            
             >n>>q; for(int i=1;i<=n;i++)cin>>a[i]; init_st(n); while(q--){ cin>>l>>r; cout<
             
              <
             
            
           
          
         
        
       
      

参考：