静态区间最值动态查询

Preface

对于两数比较大小算法[](int a, int b){return a>b?a:b;},时间复杂度为;

对于数组查询最大数，可以用如下归并算法:

int Max(int* a, int l, int r) {
	if(r==l) return a[l];
	int m = l + r >> 1;
	return max(Max(a, l, m), Max(a, m+1, r));
}
int max_val = Max(a, 0, n)

时间复杂度为;

Content

对于静态区间最值动态查询（RMQ）的描述如下：

给定一个长度为的数列，和次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数，分别表示数列的长度和询问的个数。

第二行包含个整数（记为），依次表示数列的第项。

接下来行，每行包含两个整数，表示查询的区间为。

输出格式

输出包含行，每行一个整数，依次表示每一次询问的结果。

样例输入

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

样例输出

对于常规的在线处理查询，时间复杂度为，对于很大时无法接受；

现在引入跳表(表)数据结构如下：

给定数组,查询区间之间的最（大）值query(l,r);

对于二维数组,表示一个长度为的区间之间的最大值；

那么基于倍增的思想，我们可以写出如下转移式：

对于一般的区间，在维护跳表之后，可以被拆分为两个区间之并：

于是查询可简化为query(l,r)=max(dp[l][s], dp[r-(1<<s)+1][s]);

题解如下：

# include <fstream>
# include <iostream>
# include <vector>
using namespace std;

vector<int> Log;
vector<int> a;
vector<vector<int>> dp;

void pre(int n, int m, vector<int> &a, vector<vector<int>> &dp){
    Log.push_back(0);
    Log.push_back(0);
    Log.push_back(1);
    for(int i=3;i<=n;i++) Log.push_back(Log[i>>1]+1);
    dp.resize(n+1, vector<int>(Log[n]+1));
    for(int i=1;i<=n;i++) dp[i][0]=a[i];
    for(int j=1;j<=Log[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l, int r){
    int s = Log[r-l+1];
    return max(dp[l][s], dp[r-(1<<s)+1][s]);
}
int main(){
    #ifdef DEBUG
    std::ifstream input("input.txt");
    std::ofstream output("output.txt");
    if (!input.is_open() || !output.is_open()) {
        cerr << "Failed to open input or output file." << endl;
        return 1;
    }
    std::streambuf* cinBuf = std::cin.rdbuf();
    std::streambuf* coutBuf = std::cout.rdbuf();
    std::cin.rdbuf(input.rdbuf());
    std::cout.rdbuf(output.rdbuf());
    #endif

    int n, m;
    cin>>n>>m;
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    pre(n, m, a, dp);
    while(m--){
        int l,r;
        cin>> l >> r;
        cout<<query(l,r)<<endl;
    }

    #ifdef DEBUG
    std::cin.rdbuf(cinBuf);
    std::cout.rdbuf(coutBuf);
    input.close();
    output.close();
    a.clear();
    dp.clear();
    #endif

    return 0;
}

Remark

~~嗯被快读卡住了，懒得改了~~；

事实上区间最值用线段树比较好，但是线段树对动态变化的数组威力更大，这个就是静态的数组；

也不止只有RMQ可以用st表，还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决[^1]。

[^1]: ST 表 - OI Wiki (oi-wiki.org)

跳表：静态区间最值动态查询