ST表

ST 表是用于解决 可重复贡献问题 的数据结构。可以在O(1)的时间复杂度内回答某一区间的最值查询（最小值、最大值等）。ST表使用动态规划和倍增的思想，通过预处理的方式来快速计算出各个区间的最值。

ST表的应用场合是有限的，它只能处理静态区间最值，不能维护动态的，也就是说不支持在预处理后对值进行修改。一旦修改，整张表便要重新计算，时间复杂度极高。动态最值可以用线段树、树状数组等来维护。

好的，以下是你提供的 C++ 代码，并且经过了排版和格式化，使其更加清晰：

建表部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// st[i][j] 表示以 i 为起点，包含 1<<j 个数的区间
// 以下就是递推式
// 首先，以 i 为起点，包含 1<<j 个数的区间，也就是 [i, i + (1<<j) - 1] 这个区间
// 可以拆解为：
// - 以 i 为起点的 [i, i + (1 << (j - 1)) - 1] 区间
// - 以 i + (1 << (j - 1)) 为起点的 [i + (1 << (j - 1)), i + (1 << j) - 1] 区间
// 两个区间加在一起即为完整的覆盖

// 递推公式：
// st[i][0] = a[i];
// st[i][j] = st[i][j-1] + st[i + (1 << (j - 1))][j-1];

for (int i = 0; i < n; ++i) {
    st[i][0] = a[i];  // 初始化最小区间
}
for (int j = 1; (1 << j) <= n; ++j) {
    for (int i = 0; i + (1 << j) - 1 < n; ++i) {
        st[i][j] = st[i][j - 1] + st[i + (1 << (j - 1))][j - 1];
    }
}

查表部分

1
2
3
4
5
6
7
8
9
10
// 定义两个变量 l, r 为查找区间的左右端点
// 要查区间的最值，只需分别查如图两段包含 2^x 个数的区间的最值，再进行比较，就得到所查区间的最值。

int l, r;
cin >> l >> r;
int x = log_2[r - l + 1];  // 计算区间长度的对数
cout << max(st[l][x], st[r - (1 << x) + 1][x]) << '\n';  // 比较并输出结果

// 补充：log 函数一个一个算太慢，很容易被卡，预处理一下 log_2
// log_2[i] = log_2[i >> 1] + 1;  // 预处理 log_2

预处理 log_2

1
2
3
4
// 预处理 log_2[i]，提高效率
for (int i = 2; i < MAX; ++i) {
    log_2[i] = log_2[i >> 1] + 1;
}

代码解释

  • 建表部分通过递推公式构建了一个二维数组 st，每个 st[i][j] 表示从 i 开始，长度为 2^j 的区间的和。这个表通过递推关系逐步计算得到。

  • 查表部分则使用预处理好的 log_2 数组，利用对数来快速判断区间长度，然后通过比较两个可能的区间来获取最终结果。这样做的好处是能在 O(1) 时间内得到区间的最值。

其实到这已经结束了，上题目！

【模板】ST 表

题目背景

这是一道 ST 表经典题——静态区间最大值

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 \(O(1)\)。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

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

函数返回值为读入的第一个整数。

快速读入作用仅为加快读入，并非强制使用。

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

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

1
2
3
4
5
6
7
8
9
9
7
7
9
8
7
9
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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using ll=long long;
int st[N][20];
int lg[N];
int n,m;
int main()
{
    ios::sync_with_stdio(0);
 	cin.tie(0);
 	cout.tie(0);
    cin>>n>>m;
    lg[1]=0;
    for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i][0];
    }
    for(int j=1;j<=lg[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        int t=lg[r-l+1];
        cout<<max(st[l][t],st[r-(1<<t)+1][t])<<'\n';
    }  
}