DP打表

#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;
}

时间复杂度：

这种打表方式会很紧凑，用到了许多不用的空间

ST表

基于动态规划与倍增思想，是一种更稀疏的表

定义

dp[i][j]为一个从开始，长度为的区间最值

询问

e.g.询问[0,5]

使用max(dp[0][2],dp[4][1])，即询问区间从0开始，长度为，即[0,3]，与区间从4开始，长度为即[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个长度为不相交的区间并多次求max

若区间发生重叠，我们可以取重叠区间的max

因此询问步骤如下

求出区间长度
计算dp数组中的
计算最值

预处理

将一个区间分成两半，则每一半的长度均为，后半第一个元素下标即为

处理第一个
处理后面的

时间复杂度：

注意：st表是一个静态表，适用于离线处理

板子

#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;
}

时间复杂度：

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【数据结构】ST表

DP打表

ST表

定义

询问

预处理

板子