• 基本介紹
• 模板題目
• 程式碼實現

## 基本介紹

ST表主要用於處理靜態區間最大最小值 它能做到預處理O(nlogn) 詢問O(1)的時間複雜度

f[i][j]=max(f[i][j−1],f[i 2j−1)][j−1])

f[i][j]=max(f[i][j-1],f[i 2^{j-1})][j-1])

2k<right−left 1

2^k<right-left 1

k=log(right−left 1)

k=log(right-left 1)

## 模板題目

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

9
9
7
7
9
8
7
9

​對於100%的資料，滿足：1≤N≤10^5,1≤M≤10^6​,a​i∈[0,10^9],1≤li≤r​i≤N

## 程式碼實現

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll size = 500000   1000;
ui n , m;
ui f[size][21];
ll num = 0 , f = 1;    char ch = getchar();
while(!isdigit(ch)){
if(ch == '-')   f = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num*10   ch - '0';
ch = getchar();
}
return num*f;
}
inline ll query(ll left , ll right){
ui k = log(right - left   1)/log(2);
return max(f[left][k] , f[right - (1<<k)   1][k]);
}
int main(){
n in;   m in;
for(register int i=1;i<=n;i  ){
f[i][0] in;
}
for(register int j=1;j<=20;j  )
for(int i=1;i (1<<j)-1<=n;i  )
f[i][j] = max(f[i][j - 1] , f[i   (1<<(j - 1))][j - 1]);
for(register int i=1;i<=m;i  ){
ll x , y;   x in;   y in;
printf("%d\n",query(x,y));
}
}
//COYG