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

Posted on

静态区间最值动态查询

Preface

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

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

1
2
3
4
5
6
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)

时间复杂度为$O(logN)$;

Content

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

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

输入格式

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

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

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$。

输出格式

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

样例输入

1
2
3
4
5
6
7
8
9
10
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

样例输出

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

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

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

给定数组$a[1…n]$,查询区间$(a[l],..,a[r])$之间的最（大）值query(l,r);

对于二维数组$dp[i][j]$,表示一个长度为$2^j$的区间$[i, i+2^j-1]$之间的最大值；

那么基于倍增的思想，我们可以写出如下转移式：
$$
dp[i][j]=\max(dp[i][j-1], dp[i+2^{j-1}][j-1])
$$
对于一般的区间$[s,t]$，在维护跳表之后，可以被拆分为两个区间之并：
$$
[l,r]=[l,l+2^s-1]\cup [r-2^s+1,r], s=\lfloor log_2(r-l+1) \rfloor
$$
于是查询可简化为query(l,r)=max(dp[l][s], dp[r-(1<<s)+1][s]);

题解如下：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 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)