每日热闻!数据结构：ST表学习笔记

2023-01-06 10:08:44 来源：博客园

(相关资料图)

ST表

RMQ 问题

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。ST 表是用于解决离线 RMQ 问题的一种线性数据结构，在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。

倍增思想

考虑每个长度为 2 的正整数幂的区间，这个区间的最值可以分为左右两个长度相等的区间，同时这两个区间的长度又是 2 的整数幂。所以，我们可以从小到大来递推处理出所有长度为 2 的正整数幂的区间的最值。形式化地，以最大值为例，记 \(st[i,j]\) 表示以 \(i\) 为左端点，长度是 \(2^j\) 的区间（区间\([i,i+2^j-1]\)）的最大值，分为左右两个长度相等的区间，则有

\[st[i,j]=\max(st[i,j-1],st[i+2^{j-1},j-1])\]

边界条件是 \(st[i,0]=a[i]\)，据此递推即可。（\(2^0=1\)）时间复杂度为 \(O(n \log n)\)通过两个长度为 2 的整数幂的区间，可以求出任意一个区间的最值（如下图，图来自 OI Wiki）形式化地，有

\[\max (A[l...r])=max(st[l,k],st[r-2^k+1,k])\]

其中，\(k\) 是满足 \(2^k \le r-l+1\) 的最大整数，这样可以保证两个长度是 2 的整数幂的区间把整个区间覆盖。

代码实现

洛谷 P3865 【模板】ST 表

#include #include using namespace std;#define pow2(x) (1<<(x))const int N = 1e5 + 5, M = 40;int n, m, a[N], st[N][M];inline int read() {    int x = 0, f = 1;char ch = getchar();    while (ch < "0" || ch>"9") { if (ch == "-") f = -1;ch = getchar(); }    while (ch >= "0" && ch <= "9") { x = x * 10 + ch - 48;ch = getchar(); }    return x * f;}// 1.ST 表的初始化（预处理每个长度是 2 的整数幂的区间最值）void ST_init() {    for (int i = 1;i <= n;i++) st[i][0] = a[i];    int t = log(n) / log(2);    for (int j = 1;j <= t;j++) {        for (int i = 1;i + pow2(j) - 1 <= n;i++)            st[i][j] = max(st[i][j - 1], st[i + pow2(j - 1)][j - 1]);    }}// 2.ST 表的查询int ST_query(int l, int r) {    int len = r - l + 1;    int k = log(len) / log(2);    return max(        st[l][k],        st[r - pow2(k) + 1][k]    );}int main() {    #ifndef ONLINE_JUDGE    freopen("data.in", "r", stdin);    freopen("data.out", "w", stdout);    #endif    n = read();    m = read();    for (int i = 1;i <= n;i++) a[i] = read();    ST_init();    for (int i = 1;i <= m;i++) {        // 3. 本题常数要求较高，需要进行常数优化。        int l, r;        l = read();        r = read();        // cout << ST_query(l, r) << endl;        printf("%d\n", ST_query(l, r));    }    return 0;}

关键词：数据结构用于解决时间复杂度

每日热闻!数据结构：ST表 学习笔记

ST表

RMQ 问题

倍增思想

代码实现

洛谷 P3865 【模板】ST 表

每日热闻!数据结构：ST表学习笔记