st倍增（st表）

ST表不仅能处理区间最值问题，凡是符合结合律且可重复贡献的信息查询都可以使用ST表高效进行。可重复贡献的意义在于，可以对两个交集不为空的区间进行信息合并，显然最大值、最小值、最大公约数、最小公倍数、按位或、按位与都符合这个条件。

在C++算法中，ST表的实现为以下步骤：

预处理阶段：构建一个二维数组 st [ ][ ]，其中 st[i][j] 表示从下标 i 开始、长度为 2^j 的区间内的最值（或其他查询结果）。
预处理阶段时间复杂度为 O(nlogn)，其中 n 表示数组的长度。
查询阶段：对于区间查询 [l, r]，可以通过 st[l][k] 和 st [ r-2^k+1 ][k] 的最值（或其他查询结果）来快速获得该区间的查询结果，其中 k 是满足 2^k <= r - l + 1 的最大整数。

void buildST(int n) {for (int i = 0; i < n; i++) {st[i][0] = arr[i];}for (int j = 1; (1 << j) <= 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 query(int l, int r) {int k = log2(r - l + 1);return max(st[l][k], st[r - (1 << k) + 1][k]);
}

这里详细解释一下查询代码的原理：

预处理阶段（buildST 函数）中，我们构建了一个二维数组 st，其中 st[i][j] 表示从位置 i 开始、长度为 2^j 的区间内的最大值。

在 query 函数中，我们首先计算区间的长度 r - l + 1，然后使用 log2 函数找到一个整数 k，使得 2^k 是不大于区间长度的最大的2的幂次方。这个 k 值对应了我们在预处理阶段建立的 st 数组的列索引。

接着，我们通过 st[l][k] 和 st[r - (1 << k) + 1][k] 来找到区间 [l, r] 中的最大值。这里的 (1 << k) 表达式实际上就是 2^k，它代表了以 l 为起点、长度为 2^k 的区间的左半部分，而 r - (1 << k) + 1 表示了以 r 为终点、长度为 2^k 的区间的右半部分。

通过比较这两个区间的最大值，我们可以得到区间 [l, r] 中的真正最大值。

下面一个模板题：st表模版题

模板代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) ((x)&(-x))
#define fi first
#define se second
#define PII pair<int,int>
const int inf=1e18;
const int N=1e5+10;
int a[N],st[N][20];
void buildST(int n) {for (int j = 1; (1 << j) <= 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 query(int l, int r) {int k = log2(r - l + 1);return max(st[l][k], st[r - (1 << k) + 1][k]);
}
void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];st[i][0]=a[i];}buildST(n);while(m--){int l,r;cin>>l>>r;cout<<query(l,r)<<"\n";}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//cout<<fixed<<setprecision(12); int T=1;//cin>>T;while(T--)solve();
}