ST表
给n个数，进行m次询问，每次寻找区间[l,r]中的最大值
DP打表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int arr[N];
int ans[N][N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 0;i<n;i++) cin >> arr[i];
for(int i = 0;i<n;i++){
for(int j = i;j<n;j++){
if (i==j) ans[i][j]=arr[j];
else ans[i][j]=max(ans[i][j-1],arr[j]);
}
}
int l,r;
while(m--){
cin >> l >> r;
cout << ans[l][r]<<' ';
}
return 0;
}时间复杂度：\(O(n^2+m)\)
这种打表方式会很紧凑，用到了许多不用的空间
ST表
基于动态规划与倍增思想，是一种更稀疏的表
定义
dp[i][j]为一个从\(i\)开始，长度为\(2^j\)的区间最值
询问
e.g.询问[0,5]
使用max(dp[0][2],dp[4][1])，即询问区间从0开始，长度为\(2^2=4\)，即[0,3]，与区间从4开始，长度为\(2^1=2\)即[4,5]两个区间中的max值
e.g.询问[0,13]
使用max(dp[0][3],dp[8][2]),dp[12][1])即询问区间[0,7],[8,11],[12,13]三个区间中的max值
对于任意区间都可以分解为若干个小区间求max值
因为根据二进制，任意一个整数都可以分解为若干个2的n次幂的和
因此我们可以将任意区间划分为n个长度为\(\log_2len\)不相交的区间并多次求max
若区间发生重叠，我们可以取重叠区间的max
因此询问步骤如下
- 求出区间长度\(len=r-l+1\)
- 计算dp数组中的\(j=\lfloor \log_2len\rfloor\)
- 计算最值\(ans=max(dp[l][j],dp[r-2^j-1][j])\)
预处理
将一个区间分成两半，则每一半的长度均为\(2^{j-1}\)，后半第一个元素下标即为\(i+2^{j-1}\)
- 处理第一个\(dp[i][0]=arr[i]\)
- 处理后面的\(dp[i][j]=max(dp[i][j-1],dp[i+2^{i-1}][j-1])\)
时间复杂度：\(O(n\log n)\)
注意：st表是一个静态表，适用于离线处理
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits\stdc++.h>
using namespace std;
vector<vector<int>> dp;
int query(int l,int r){
int j = (int)log2(r-l+1);
return max(dp[l][j],dp[r-(1<<j)+1][j]);
}
int main(){
vector<int> arr = {9,3,1,7,5,6,0,8};
const int N = 8;
// 预处理
dp = vector<vector<int>> (N,vector<int>((int)log2(N)+5,0)); // 初始化dp数组
for (int i = 0;i < N;i++) dp[i][0]=arr[i];
for (int j= 1;j<=log2(N);j++){
for (int i = 0; i+(1<<j)-1<N;i++){
dp[i][j]= max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
// 询问
int l, r;
while(cin >> l >> r){
cout << query(l,r) << endl;
}
return 0;
}时间复杂度：\(O(n\log n+m)\)