c++算法之基本算法篇

C++初学者建议：掌握基本语法，理解STL，通过算法书籍提升逻辑思维 #生活技巧# #工作学习技巧# #编程语言学习路径#

一、倍增法：像爬楼梯一样高效解决问题

1.1 什么是倍增法？生活中的比喻

想象一下你正在爬一座很高的楼梯：

普通爬法：每次只爬1级台阶，要爬1000级就需要1000步倍增爬法：第一次爬1级，第二次爬2级，第三次爬4级，第四次爬8级…这样爬1000级只需要约10步（因为1+2+4+8+…+512=1023）

倍增法就像这种"指数级爬楼梯"的策略：每次处理的问题规模都是上一次的两倍，从而实现指数级的效率提升。

1.2 技术定义

倍增法（Binary Lifting）是一种通过预处理信息，使得每次查询或操作能够以对数时间复杂度完成的算法。其核心思想是：

预处理：计算并存储所有2的幂次步长（1,2,4,8,…）的信息查询：将任意步长分解为若干2的幂次步长的组合 1.3 为什么叫"倍增法"？

这个名字非常形象：

“倍”：每次处理的问题规模都是上一次的两倍“增”：逐步增加处理规模合起来就是"每次规模翻倍增长的方法" 1.4 倍增法的核心思想

倍增法的精髓在于二进制分解。任何整数都可以表示为若干2的幂次之和：

13 = 8 + 4 + 1 = 2³ + 2² + 2⁰

倍增法利用这一特性，将复杂问题分解为若干个已经预处理好的2的幂次问题。

1.5 倍增法的典型应用 应用场景问题描述倍增法作用树上LCA求两节点的最近公共祖先预处理每个节点的2^k级祖先RMQ求区间最值预处理所有2^k长度的区间最值快速幂计算a^b将b分解为二进制，逐步计算字符串匹配KMP算法的优化预处理部分匹配表

二、ST算法：用"稀疏表"快速查询区间最值

2.1 什么是ST算法？生活中的比喻

想象你有一个超级记忆力强的朋友：

你问他：“1号到8号位置的最高气温是多少？” 他立即回答你问他：“3号到6号位置的最高气温是多少？” 他也立即回答你问他：“5号到7号位置的最高气温是多少？” 他还是立即回答

这位朋友之所以这么快，是因为他提前记住了所有可能的2的幂次长度的区间最值（如1-2,3-4,5-6,…；1-4,5-8,…；1-8,…）。当被问任意区间时，他只需组合两个已知的区间即可快速回答。

ST算法（Sparse Table，稀疏表）就是这种提前预处理所有2的幂次长度区间信息的技术。

2.2 技术定义

ST算法是一种用于解决静态区间查询问题（特别是RMQ问题）的高效算法。它通过预处理构建一个二维数组（稀疏表），存储所有长度为2^k的区间信息，使得任意区间查询可以在O(1)时间内完成。

2.3 为什么叫"ST算法"？ "S"代表Sparse（稀疏）：虽然存储了所有2的幂次长度的区间，但相比存储所有可能区间，空间复杂度大大降低"T"代表Table（表）：使用二维表格存储预处理信息合起来就是"稀疏表算法" 2.4 ST算法的核心思想

ST算法的核心是区间重叠技术：

预处理：计算所有长度为2^k的区间最值查询：对于任意查询区间[L,R]，找到两个长度为2^k的区间，它们覆盖[L,R]且重叠部分不影响结果

例如查询[3,7]：

找到k=2（因为2²=4 ≤ 7-3+1=5）查询区间[3,6]和[4,7]（两个长度为4的区间）取这两个区间最值的最大值/最小值 2.5 ST算法的预处理过程 初始化：长度为1的区间（即单个元素）的最值就是元素本身

st[i][0] = arr[i] // 所有长度为2^0=1的区间 递推计算：利用动态规划计算更长的区间

st[i][j] = merge(st[i][j-1], st[i + (1<<(j-1))][j-1])

其中merge函数根据需求取min或max

对数预处理：提前计算每个长度对应的k值，加速查询

log_table[i] = log2(i) // 向下取整

三、倍增法与ST算法的实现

3.1 倍增法实现：树上LCA问题

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

const int MAXN = 100005;

const int LOGN = 20; // 足够大的log值

vector<int> tree[MAXN]; // 邻接表表示树

int depth[MAXN]; // 节点深度

int parent[MAXN][LOGN]; // parent[i][j]表示节点i的2^j级祖先

// DFS预处理深度和直接父节点

void dfs(int node, int par, int dep) {

depth[node] = dep;

parent[node][0] = par;

for (int child : tree[node]) {

if (child != par) {

dfs(child, node, dep + 1);

}

}

}

// 倍增预处理

void preprocess(int root, int n) {

dfs(root, -1, 0); // 初始化深度和直接父节点

// 填充倍增表

for (int j = 1; j < LOGN; j++) {

for (int i = 1; i <= n; i++) {

if (parent[i][j-1] != -1) {

parent[i][j] = parent[parent[i][j-1]][j-1];

} else {

parent[i][j] = -1;

}

}

}

}

// LCA查询

int lca(int u, int v) {

// 确保u在更深层

if (depth[u] < depth[v]) {

swap(u, v);

}

// 将u提升到与v同一深度

int diff = depth[u] - depth[v];

for (int j = LOGN-1; j >= 0; j--) {

if (diff & (1 << j)) {

u = parent[u][j];

}

}

// 如果u和v相同，直接返回

if (u == v) {

return u;

}

// 同时提升u和v，直到它们的父节点相同

for (int j = LOGN-1; j >= 0; j--) {

if (parent[u][j] != parent[v][j]) {

u = parent[u][j];

v = parent[v][j];

}

}

return parent[u][0];

}

int main() {

int n = 7; // 节点数

// 构建树结构

tree[1].push_back(2);

tree[2].push_back(1);

tree[1].push_back(3);

tree[3].push_back(1);

tree[2].push_back(4);

tree[4].push_back(2);

tree[2].push_back(5);

tree[5].push_back(2);

tree[3].push_back(6);

tree[6].push_back(3);

tree[3].push_back(7);

tree[7].push_back(3);

preprocess(1, n); // 以1为根节点预处理

cout << "LCA(4, 5): " << lca(4, 5) << endl; // 输出2

cout << "LCA(6, 7): " << lca(6, 7) << endl; // 输出3

cout << "LCA(4, 6): " << lca(4, 6) << endl; // 输出1

return 0;

}

3.2 ST算法实现：区间最大值查询

#include <iostream>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

class SparseTable {

private:

vector<vector<int>> st; // 稀疏表

vector<int> log_table; // 对数表

int n; // 数组长度

public:

// 构造函数，初始化稀疏表

SparseTable(const vector<int>& arr) {

n = arr.size();

int k = log2(n) + 1;

st.assign(n, vector<int>(k));

log_table.assign(n + 1, 0);

// 预处理对数表

for (int i = 2; i <= n; i++) {

log_table[i] = log_table[i / 2] + 1;

}

// 初始化长度为1的区间

for (int i = 0; i < n; i++) {

st[i][0] = arr[i];

}

// 动态规划构建稀疏表

for (int j = 1; j < k; 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]);

}

}

}

// 查询区间[L, R]的最大值

int query(int L, int R) {

int j = log_table[R - L + 1];

return max(st[L][j], st[R - (1 << j) + 1][j]);

}

};

int main() {

vector<int> arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};

SparseTable st(arr);

cout << "Max in [0, 4]: " << st.query(0, 4) << endl; // 输出9

cout << "Max in [2, 7]: " << st.query(2, 7) << endl; // 输出7

cout << "Max in [5, 9]: " << st.query(5, 9) << endl; // 输出8

return 0;

}

四、倍增法与ST算法的比较

特性倍增法ST算法核心思想预处理2的幂次步长信息预处理所有2的幂次长度区间时间复杂度预处理O(n log n)，查询O(log n)预处理O(n log n)，查询O(1)空间复杂度O(n log n)O(n log n)适用场景树上路径查询、动态规划优化静态区间查询（RMQ）灵活性可处理动态更新（结合其他技术）仅适用于静态数组实现难度中等简单典型应用LCA、KMP优化、快速幂RMQ、静态区间统计 4.1 选择建议

选择倍增法：

需要处理树上的路径查询（如LCA）问题可以分解为2的幂次步长的组合需要支持动态更新（结合其他数据结构）

选择ST算法：

需要处理静态数组的区间查询查询操作非常频繁，需要O(1)时间数组内容不会改变（或改变不频繁）

五、实际应用举例

5.1 倍增法应用：网络路由中的路径查找

在计算机网络中，路由器需要快速找到数据包的传输路径。使用倍增法可以：

预处理每个路由器的2^k级上游路由器当需要查找从A到B的路径时：先找到A和B的最近公共祖先路由器C然后分别从A到C和B到C的路径组合起来

这种方法比传统DFS/BFS快得多，特别适合大型网络。

5.2 ST算法应用：股票分析中的区间最大值

在金融分析中，经常需要查询某段时间内的最高股价：

预处理所有2的幂次天数区间内的最高股价当分析师查询"从第3天到第10天的最高股价"时：计算区间长度8天查询[3,6]和[7,10]两个区间的最大值取两者中的较大值

ST算法使这种查询可以在常数时间内完成，非常适合高频交易系统。

5.3 综合应用：社交网络中的共同好友推荐

在社交网络中，要找到两个用户的共同好友：

使用倍增法构建用户关系树使用ST算法快速查询两个用户的关系路径在路径上分析共同好友特征

这种组合应用可以高效实现个性化推荐系统。

六、性能优化与注意事项

6.1 倍增法优化技巧 合理选择LOG值：

const int LOGN = 20; // 对于10^6规模的数据足够

过大会浪费空间，过小会导致错误。

位运算优化：

// 使用位运算代替乘除法

parent[i][j] = parent[parent[i][j-1]][j-1];

// 比 parent[i][j] = parent[i][j-1]的2^(j-1)级祖先 更快

内存布局优化：

// 使用一维数组模拟二维数组，提高缓存命中率

int parent[MAXN * LOGN];

6.2 ST算法优化技巧 快速对数计算：

// 预处理对数表，避免实时计算

for (int i = 2; i <= n; i++) {

log_table[i] = log_table[i >> 1] + 1;

}

查询优化：

// 使用位运算计算区间长度

int j = log_table[R - L + 1];

// 比 j = (int)log2(R - L + 1) 更快

空间优化：

struct Pair {

int max_val, min_val;

};

vector<vector<Pair>> st;

6.3 常见陷阱与解决方案 问题原因解决方案倍增法查询错误深度计算错误确保DFS时正确计算深度ST数组越界预处理范围不足检查(1 << j) <= n查询结果不准确区间重叠处理不当确保两个覆盖区间有重叠内存超限LOG值设置过大根据数据规模合理设置LOGN时间超限预处理或查询效率低使用位运算和缓存优化

七、总结与展望

7.1 核心要点回顾

倍增法：

核心思想：预处理2的幂次步长信息时间复杂度：预处理O(n log n)，查询O(log n)适用场景：树上路径查询、可分解问题

ST算法：

核心思想：预处理所有2的幂次长度区间时间复杂度：预处理O(n log n)，查询O(1)适用场景：静态区间查询（RMQ） 7.2 学习建议

从简单问题入手：

先实现简单的RMQ问题再尝试树上LCA问题最后挑战复杂应用

可视化理解：

画出倍增表和稀疏表的结构手动模拟查询过程理解二进制分解的原理

实践应用：

在LeetCode上练习相关题目尝试在实际项目中应用这些算法分析不同算法的性能差异 7.3 进阶方向

算法扩展：

学习线段树、树状数组等更通用的区间查询结构研究动态版本的处理方法探索多维问题的解决方案

应用领域：

计算机图形学中的光线追踪生物信息学中的序列比对人工智能中的决策树优化

倍增法和ST算法是算法设计中的经典思想，它们体现了"空间换时间"和"分治"的重要策略。掌握这些算法不仅能解决特定问题，更能培养你的算法思维，为学习更高级的数据结构和算法打下坚实基础。

希望这篇详细的指南能帮助你彻底理解C++中的倍增法与ST算法，并在实际编程中灵活运用！

网址：c++算法之基本算法篇 https://www.yuejiaxmz.com/news/view/1334999

相关内容

算法训练 简单加法(基本型)
项目五 描述洗衣流程认识算法——了解算法及基本控制结构 课件(共25张PPT)
音频3A算法之
c语言常见排序算法
群体智能算法之蚁群算法初探(二)
c语言程序理财划算器,基金A和C哪个划算？基金投资省钱秘籍！
零基础科普：4种简单推荐算法背后的原理
蚁群算法
贪心算法详解
五大经典算法

随便看看