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

基本介紹

在好奇心的驅使下學習了st表 最後發現沒怎麼懂 不過我知道它很快 – –

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

設f[i][j]表示區間[i,i 2^j-1]的最大值 f[i][0]為序列初值
狀態轉移方程為

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])
對於任意一個詢問的區間[left,right]我們把它拆成兩段長度為2^k的區間 再取最大值 k滿足

2k<right−left 1

2^k<right-left 1
因為k要取最大 所以

k=log(right−left 1)

k=log(right-left 1)
我們已經預處理了log1 – logn 也就很好搞了

模板題目

題目背景
這是一道ST表經典題——靜態區間最大值
請注意最大資料時限只有0.8s,資料強度不低,請務必保證你的每次查詢複雜度為 O(1) O(1)

題目描述
給定一個長度為 N N 的數列,和 M M 次詢問,求出每一次詢問的區間內數字的最大值。

輸入輸出格式
輸入格式:
第一行包含兩個整數 N, M,分別表示數列的長度和詢問的個數。
第二行包含 N N 個整數(記為 a​i),依次表示數列的第 i i 項。
接下來 M M行,每行包含兩個整數l​i​​ ,r​i,表示查詢的區間為[l​i,r​i]
輸出格式:
輸出包含 M M行,每行一個整數,依次表示每一次詢問的結果。

輸入輸出樣例
輸入樣例:
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

說明
對於30%的資料,滿足:1≤N,M≤10
對於70%的資料,滿足:1≤N,M≤10^5
​對於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;
#define in = read();
typedef long long ll;
typedef unsigned int ui;
const ll size = 500000   1000;
ui n , m;
ui f[size][21];
inline ll read(){
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