C++前缀和优化区间求和算法详解

这段代码实现了一个简单的区间求和查询程序。它通过嵌套循环的方式，对每次询问遍历区间内的所有元素来计算总和。当数据规模较大时，这种实现的时间复杂度会变得很高。 ## 🎯 优化方案 **前缀和优化**是最常用的优化方法，可以将每次查询的时间复杂度降低到 O(1)： ```cpp #include <iostream> using namespace std; const int MAXN = 100005; // 根据题目实际数据范围调整 long long a[MAXN], prefix[MAXN]; int main() { int n, q; cin >> n >> q; // 输入花朵鲜艳值并计算前缀和 for (int i = 1; i <= n; i++) { cin >> a[i]; prefix[i] = prefix[i-1] + a[i]; } // 处理 q 次询问 for (int i = 0; i < q; i++) { int L, R; cin >> L >> R; // 使用前缀和公式 O(1) 计算区间和 cout << prefix[R] - prefix[L-1] << endl; } return 0; } ``` ## 📊 时间复杂度对比 | 实现方式 | 预处理 | 每次查询 | |---------|--------|---------| | 原始代码 | O(n) | O(R-L+1) | | 前缀和优化 | O(n) | O(1) | ## 💡 代码说明 - **原始代码问题**：每次询问都需要遍历区间内的所有元素，时间复杂度为 O(n×q) - **优化方案**：使用前缀和数组 `prefix[i]` 存储前 i 个元素的和 - **计算公式**：区间 [L,R] 的和 = prefix[R] - prefix[L-1] - **注意数据类型**：建议使用 `long long` 类型避免整数溢出 ## ⚠️ 开发注意事项 1. 处理大量输入时使用 `scanf`/`printf` 或关闭流同步 2. 考虑使用 `vector` 替代静态数组，更灵活且安全 3. 数组索引从 1 开始可以简化边界条件处理 ######[AI问答 | 490点数解答 | 2026-06-20 22:11:10]