在 C++ 中，"倍增"（也称为"指数增长"或"指数级别增长"）是一种算法优化技术，它通常用于解决一些需要频繁查询某个区间内的信息的问题，例如在处理动态规划、搜索等算法中。倍增思想的主要目的是通过预处理和存储一些中间结果，以加速后续的查询操作。
具体来说，倍增思想通常包括以下步骤：
-
预处理阶段：在预处理阶段，计算和存储一些中间结果，通常是按指数级别递增的步长。这些中间结果可以是某个位置到其 2^k（k 为整数）步后的位置的信息。
-
查询阶段：在查询阶段，通过利用预处理阶段的中间结果，可以快速获取到所需的信息，而不必每次都进行全面的计算。
倍增思想的优点在于它通过空间换时间的方式来提高查询效率，尤其在需要频繁查询某个区间内信息的情况下，可以显著减少计算量。
ST表（Sparse Table）是一种用于高效处理区间查询问题的数据结构，常用于解决静态数组的区间查询问题，如区间最值。ST表的主要思想是预处理出一个二维数组，使得对于任意区间 [l, r]，可以在 O(1) 的时间复杂度内得到其区间查询结果。
在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 = 0; i + (1 << j) <= n; i++) {
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}
}
}预处理原理：首先默认最大值st[i][0]对应的当前i的位置最大值就是自己。 然后更新每个在n范围内的（i,j）对应的st[i][j]的值，用上述式子，具体可以比划感受一下为什么是这样的式子。此时是按两个两个，四个四个，八个八个的方式在更新st数组。
查询代码（最大值）示例：
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]中的真正最大值。
以下是完整的示例代码：
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100005;
const int LOGMAXN = 20; // log2(MAXN) + 1
int *arr;
int **st;
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 = 0; i + (1 << j) <= 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]);
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
arr = new int[n];
st = new int*[n];
for (int i = 0; i < n; i++) {
st[i] = new int[LOGMAXN];
}
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
buildST(n);
cout << "Built ST table for array:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; (1 << j) <= n; j++) {
cout << st[i][j] << " ";
}
cout << endl;
}
int l, r;
cout << "Enter the range [l, r] for query: ";
cin >> l >> r;
cout << "Maximum value in range [" << l << ", " << r << "] is: " << query(l, r) << endl;
delete[] arr;
for (int i = 0; i < n; i++) {
delete[] st[i];
}
delete[] st;
return 0;
}P1. 洛谷p2880Balanced lineup G
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100005;
const int LOGMAXN = 20; // log2(MAXN) + 1
int *arr;
int **st;
int **stmin;
void buildST(int n) {
for (int i = 0; i < n; i++) {
st[i][0] = arr[i];
stmin[i][0]=arr[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
stmin[i][j] = min(stmin[i][j-1], stmin[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])-min(stmin[l][k], stmin[r - (1 << k) + 1][k]);
}
int main() {
int n;cin >> n;
int q;cin>>q;
arr = new int[n];
st = new int*[n];
stmin = new int*[n];
for (int i = 0; i < n; i++) {
st[i] = new int[LOGMAXN];
stmin[i] = new int[LOGMAXN];
}
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
buildST(n);
for(int i=1;i<=q;i++)
{
int l, r;
cin >> l >> r;
cout <<query(l-1, r-1) << endl;//题目是1作为索引开头
}
return 0;
}