RMQ-ST表

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
using namespace std;
const int o_o=5e4+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
int dpmax[o_o][21];
int dpmin[o_o][21];
int n,q,l,r;
int lg[o_o];
lg[0]=lg[1]=0;
int main(){
for(int i=2;i<o_o;i++)lg[i]=lg[i>>1]+1;
  for(itn i=0;i<o_o;i++)
  for(int j=0;j<21;j++)
  dpmin[i][j]=oo,dpmax[i][j]=0;
  cin>>n>>q;
  for(int i=1;i<=n;i++){
      int u;scanf("%d",&u);
      dpmax[i][0]=dpmin[i][0]=u;
  }
  for(int j=1;j<=lg[n];j++){
      for(int i=1;i<=n;i++){
          if(i+(1<<j)-1<=n){
              dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<j-1)][j-1]);
              dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<j-1)][j-1]);
          }
      }
  }倍增思想画图就出来了
  while(q--){
      scanf("%d%d",&l,&r);
      int k=lg[r-l+1];
      printf("%d\n",max(dpmax[l][k],dpmax[r+1-(1<<k)][k])-min(dpmin[l][k],dpmin[r+1-(1<<k)][k]));
  }
}