ST表板子题 O(nlogn)--O(1)

问区间内最大数和最小数的差是多少？

建两个表就行了一个维护区间最大值，一个维护区间最小值。

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
const int maxn = 5e4+5;int h[maxn];
int b[maxn][21],x[maxn][21];
int q,n;
void mkst() {for(int j=1; j<=21; j++) {for(int i=1; i+(1<<j)-1<=n; i++) {b[i][j] = max(b[i][j-1],b[i+(1<<(j-1))][j-1]);x[i][j] = min(x[i][j-1],x[i+(1<<(j-1))][j-1]);}}
}
int main() {scanf("%d%d",&n,&q);for(int i=1; i<=n; i++) {scanf("%d",&h[i]),b[i][0] = x[i][0] = h[i];}mkst();int l,r;while(q--) {scanf("%d%d",&l,&r);int k = log2(r-l+1);int a1 = max(b[l][k],b[r-(1<<k)+1][k]);int a2 = min(x[l][k],x[r-(1<<k)+1][k]);printf("%d\n",a1-a2);}return 0;
}

ST表的二维一般只需开到21即可，因为2^21次方 2097152 > 1e6 

询问中的k = log2(r-l+1)，即 2^(log2(r-l+1) == r-l+1;