倍增与 ST 表
倍增
倍增即成倍增长。是指我们在进行递推时，如果状态空间很大，线性递推无法满足时空要求，此时可以考虑成倍增长的方式，只递推状态空间在
算法竞赛进阶指南原书例题：给定一个长度为
倍增算法：
- 令
- 比较“
数组中 之后的 个数的和”与 的大小，也就是说，如果 ，则令 ，即累加上这 个数的和，然后把 的跨度增长一倍。否则 。 - 当
为 时，结束循环，此时 即为答案。
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], t, s[N];
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
int p = 1, k = 0, sum = 0;
while(p) {
if (k + p <= n && sum + s[k + p] - s[k] <= t) {
sum += s[k + p] - s[k];
k += p;
p *= 2;
} else {
p /= 2;
}
}
cout << k << endl;
return 0;
}问题思考：AcWing 109. 天才 ACM
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll t, n, m, K, a[N], tot, b[N];
bool calc(ll l,ll k,ll p) {
ll res = 0;
for(ll i = l; i <= k + p; i++) b[i - l] = a[i];
ll len = p + k - l + 1;
sort(b, b + len);
if (len >= 2 * m) {
for(ll i = 0; i < m; i++) {
res += (b[i] - b[len - i - 1]) * (b[i] - b[len - i - 1]);
}
} else {
ll temp = len / 2;
for(ll i = 0; i < temp; i++) {
res += (b[i] - b[len - i - 1]) * (b[i] - b[len - i - 1]);
}
}
if (res <= K) return true;
return false;
}
int main() {
cin >> t;
while (t--) {
tot = 0;
cin >> n >> m >> K;
for (ll i = 0; i < n; i++) cin >> a[i];
ll l = 0;
while (l < n) {
ll k = l, p = 1;
while (p) {
if (calc(l, k, p) && k + p < n) {
k += p;
p *= 2;
} else {
p /= 2;
}
}
tot++;
l = k + 1;
}
cout << tot << endl;
}
return 0;
}ST 表
ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。
例如：给定 [l, r] 的最大值。
朴素想法：考虑使用区间 DP，
- 枚举所有的左端点和右端点，记录所有区间的最大值，用
f[i][j]来表示区间[i, j]的最大值。 - 状态转移，考虑当前状态
f[i][j]由何状态转变而来？当前区间[i][j]最后加入进来的值可能时也可能是 - 选
： f[i][j] = max(f[i + 1][j], a[i]) - 选
： f[i][j] = max(f[i][j - 1], a[j])
- 选
- 状态转移方程：
f[i][j] = max(max(f[i][j - 1], a[j]), max(f[i + 1][j], a[i])) - 边界条件：
i == j时f[i][j] = a[i] - cpp
for (int len = 1; len <= n; len++) { // 区间长度 for (int i = 1; i + len - 1 <= n; i++) { // 左端点 int j = i + len - 1; // 右端点 if (i == j) f[i][j] = a[i]; else f[i][j] = max(max(f[i][j - 1], a[j]), max(a[i], f[i + 1][j])); } } - 问题与思考：时间复杂度？空间复杂度？有没有更好的状态表示？
算法思想
ST 表基于倍增思想，预处理时间复杂度为
具体实现如下：
预处理
- 令
表示区间 的最大值， 。 - 状态转移方程：
。
查询
对于每一个询问，可以将其分成两部分：
算法实现
cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 18;
int a[N], f[N][20], n, m, lg2[N];
void init() {
for (int j = 0; j < M; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = a[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = lg2[r - l + 1];
// 使用cmath 中的 log函数 以10为底
// int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) lg2[i]= lg2[i >> 1] + 1;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
init();
while (m--) {
int x, y; scanf("%d%d", &x, &y);
printf("%d\n", query(x, y));
}
return 0;
}注意：可以预处理