今日学习内容:倍增与ST表
知识点总结
倍增
在 C++ 里,倍增是一种很实用的算法思想,其核心是借助不断翻倍的方式,在对数时间内达成原本需要线性时间才能完成的操作。下面为你介绍几个常见的应用场景:
1. 快速幂运算
快速幂运算是倍增思想的典型应用,它能够高效地计算出 a^n 的值,时间复杂度仅为 O (log n) 。
code
int fastPow(int a, int n) {
int res = 1;
while (n > 0) {
if (n % 2 == 1) {
res = res * a;
}
a = a * a;
n = n / 2;
}
return res;
}
在上述代码中,我们把指数 n
按二进制进行分解,对于每一位为 1 的部分,就将对应的幂次累乘到结果里。
2. 最近公共祖先(LCA)
在处理树结构问题时,利用倍增法可以在预处理后,以 O (log n) 的时间复杂度快速找到两个节点的最近公共祖先。
code
const int MAXN = 100005;
const int LOGN = 20; // 足够处理2^20个节点
vector<int> adj[MAXN];
int parent[MAXN][LOGN]; // parent[u][k] 表示节点u的第2^k个祖先
int depth[MAXN];
void dfs(int u, int p) {
parent[u][0] = p;
depth[u] = depth[p] + 1;
for (int k = 1; k < LOGN; k++) {
parent[u][k] = parent[parent[u][k-1]][k-1];
}
for (int v : adj[u]) {
if (v != p) {
dfs(v, u);
}
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
// 让u和v处于同一深度
for (int k = LOGN-1; k >= 0; k--) {
if (depth[u] - (1 << k) >= depth[v]) {
u = parent[u][k];
}
}
if (u == v) return u;
// 同时向上跳跃
for (int k = LOGN-1; k >= 0; k--) {
if (parent[u][k] != parent[v][k]) {
u = parent[u][k];
v = parent[v][k];
}
}
return parent[u][0];
}
该算法先通过预处理构建出每个节点的第 2^{k} 级祖先,之后借助二进制分解来实现快速跳跃。
3. 稀疏表(Sparse Table)
稀疏表常用于解决静态区间的最值查询问题(RMQ),其预处理时间为 O (n log n),查询时间为 O (1)。
code
const int MAXN = 100005;
const int LOGN = 20;
int arr[MAXN];
int st[MAXN][LOGN]; // st[i][k] 表示区间[i, i+2^k-1]的最小值
void build() {
int n = 100000; // 假设有n个元素
for (int i = 0; i < n; i++) {
st[i][0] = arr[i];
}
for (int k = 1; k < LOGN; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[i][k] = min(st[i][k-1], st[i + (1 << (k-1))][k-1]);
}
}
}
int query(int l, int r) {
int len = r - l + 1;
int k = 31 - __builtin_clz(len); // 计算k = log2(len)
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
稀疏表的原理是利用倍增思想,把每个区间分解成两个长度为 2^k 的子区间,进而实现高效查询。
核心思想总结
倍增法的核心在于:
- 预处理出 2^k 规模的信息。
- 利用二进制分解,将大问题转化为多个小问题进行求解。
- 最终把时间复杂度从 O (n) 优化到 O (log n)。
这种算法思想在处理各种需要快速查询或递推的场景中都十分有效。
ST表
在 C++ 中,ST 表( Sparse Table )是一种用于高效处理静态区间查询问题的数据结构,特别适合解决区间最值查询( RMQ, Range Minimum/Maximum Query )问题。它的核心思想是倍增和动态规划,通过预处理实现 O (n log n) 的时间复杂度,查询则可达到 O (1) 的时间复杂度。
原理与结构
ST 表的核心是利用动态规划预处理出所有长度为 2 的幂的区间的信息。对于数组arr
,定义st[i][k]
表示从位置i
开始,长度为 2^k 的区间的最值。例如:
st[i][0]
就是arr[i]
(区间长度为 1)st[i][1]
是区间[i, i+1]
的最值(长度为 2)st[i][2]
是区间[i, i+3]
的最值(长度为 4)- 以此类推…
预处理过程
预处理时,我们通过动态规划递推公式:
st[i][k] = min(st[i][k-1], st[i + 2^(k-1)][k-1])
即把长度为 2^k 的区间拆成两个长度为 2^{k-1} 的子区间,取它们的最值。
查询过程
查询区间[l, r]
时,找到最大的k
使得 2^k ≤ r-l+1,然后用两个重叠的长度为 2^k 的子区间覆盖原区间:
- 第一个区间从
l
开始,长度为 2^k - 第二个区间以
r
结束,长度为 2^k
这两个子区间的最值的组合即为原区间的最值。
代码实现
下面是 ST 表处理区间最小值查询(RMQ)的完整代码:
code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
const int LOG = 20; // 处理2^20 = 1e6范围内的数据
int arr[MAXN];
int st[MAXN][LOG]; // st[i][k]表示区间[i, i+2^k-1]的最小值
int log2_table[MAXN]; // 预计算log2的值,加速查询
// 预处理ST表和log2_table
void build(int n) {
// 预处理log2_table
log2_table[1] = 0;
for (int i = 2; i <= n; i++) {
log2_table[i] = log2_table[i/2] + 1;
}
// 初始化st[i][0]
for (int i = 0; i < n; i++) {
st[i][0] = arr[i];
}
// 动态规划构建ST表
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[i][k] = min(st[i][k-1], st[i + (1 << (k-1))][k-1]);
}
}
}
// 查询区间[l, r]的最小值
int query(int l, int r) {
int len = r - l + 1;
int k = log2_table[len];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
int n, q;
cin >> n; // 输入数组长度
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
build(n); // 预处理
cin >> q; // 输入查询次数
while (q--) {
int l, r;
cin >> l >> r; // 查询区间[l, r](下标从0开始)
cout << query(l, r) << endl;
}
return 0;
}
使用示例
假设有数组 [4, 6, 1, 5, 7, 3]
,预处理后可以快速查询任意区间的最小值:
- 查询区间
[1, 3]
(即[6, 1, 5]
)的最小值为1
- 查询区间
[0, 5]
(整个数组)的最小值为1
复杂度分析
- 预处理时间:O(n log n)
- 查询时间:O (1) (每个查询)
- 空间复杂度:O(n log n)
ST 表的局限性在于只能处理静态数据(即预处理后不能修改数组),且不适合需要频繁更新的场景。对于动态数据,可以考虑使用线段树等其他数据结构。