（ST表裸题）

ST表是一种很优雅的算法，用于求静态RMQ

数组l[i][j]表示从i开始，长度为2^j的序列中的最大值

注意事项：

1.核心部分：

for(int j = 1; (1<
     
      <= n; j++)        for(int i = 1; i+(1<
      
       <= n; i++) {            l[i][j] = max(l[i][j-1],l[i+(1<<(j-1))][j-1]);            s[i][j] = min(s[i][j-1],s[i+(1<<(j-1))][j-1]);        }
      
     

因为i~j的位数是j-i+1位，所以循环的边界需要-1，而所求的两段区间是不相交的，所以循环内不用-1（或者说，-1又+1了）

2.位运算需要频繁地打括号

 

代码如下

#include
     
      #include
      
       using namespace std;const int maxn = 50005;int n,q;int a[maxn],l[maxn][50],s[maxn][50];int al,as,x,y;int main() {    scanf("%d%d",&n,&q);    for(int i = 1; i <= n; i++){        scanf("%d",&a[i]);        l[i][0] = a[i];        s[i][0] = a[i];    }    for(int j = 1; (1<
       
        <= n; j++)        for(int i = 1; i+(1<
        
         <= n; i++) {            l[i][j] = max(l[i][j-1],l[i+(1<<(j-1))][j-1]);            s[i][j] = min(s[i][j-1],s[i+(1<<(j-1))][j-1]);        }    while(q) {        q--;        scanf("%d%d",&x,&y);        int k = 0;        while(x+(1<<(k+1))<= y)k++;        al = max(l[x][k],l[y-(1<