ST表
2025-06-01 20:25:35
发布于：北京
47阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int n, m;
int s[1000005];
int st_max[1000005][30];
//st_max[i][j] 记录 [i,i+2^j-1] 这个区间的最大值
//左端点是 i ，长度是 2^j
void ST_Init() {
//第一步，初始化
for (int i = 1; i <= n; i++) {
st_max[i][0] = s[i];
}
//第二步，根据 状态转移方程 打表
int k = log2(n);
//枚举区间长度 2^j
for (int j = 1; j <= k; j++) {
//枚举左端点
//要保证右端点不越界
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
//分成两个长度是 2^(j-1) 的小区间
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
}
}
}
// 查询 [l,r] 这个区间的最大值（包含左右端点）
int get_max(int l, int r) {
//计算出小于等于 区间长度最大的 2 的整数次幂 1 2 4 8 16 ....
int k = log2(r - l + 1);
//答案 = MAX (左端点为 l 长度是 2^k 的区间 , 右端点为 r 长度是 2^k 的区间)
//因为这两个区间 完整覆盖了查询区间
return max(st_max[l][k], st_max[r - (1 << k) + 1][k]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
ST_Init();
while (m--) {
int l, r;
cin >> l >> r;
cout << get_max(l, r) << endl;
}
return 0;
}
有帮助，赞一个