C++实现区间更新并找出最大值的高效方法

以下是针对该问题的分析与修正后的代码： ### 错误分析 在原问题描述中未给出错误代码，不过此问题的关键在于处理区间更新及找出最终数组中的最大值。一般而言，若直接对区间 `[L, R]` 内的每个元素都加上 `K`，时间复杂度会达到 $O(q * n)$，在 `n` 和 `q` 较大时效率不高。可以运用差分的方法，把区间更新的时间复杂度优化到 $O(1)$，最后再通过前缀和恢复原数组，找出最大值。 ### 修正后的代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; // 输入 n 和 q cin >> n >> q; // 存储原始数组 vector<int> a(n + 1, 0); // 存储差分数组 vector<int> diff(n + 2, 0); // 输入 n 个正整数 for (int i = 1; i <= n; ++i) { cin >> a[i]; // 初始化差分数组 diff[i] = a[i] - a[i - 1]; } // 进行 q 次操作 for (int i = 0; i < q; ++i) { int L, R, K; cin >> L >> R >> K; // 对差分数组进行区间更新 diff[L] += K; diff[R + 1] -= K; } // 通过前缀和恢复原数组 for (int i = 1; i <= n; ++i) { a[i] = a[i - 1] + diff[i]; } // 找出数组中的最大值 int max_val = *max_element(a.begin() + 1, a.end()); // 输出最大值 cout << max_val << endl; return 0; } ``` ### 代码解释 1. **输入处理**：先输入 `n` 和 `q`，接着输入 `n` 个正整数，同时初始化差分数组 `diff`。 2. **区间更新**：在每次操作中，输入 `L`、`R` 和 `K`，对差分数组 `diff` 进行更新，`diff[L] += K` 表示从 `L` 开始加上 `K`，`diff[R + 1] -= K` 表示在 `R + 1` 处减去 `K`，以此保证只在 `[L, R]` 区间内加上 `K`。 3. **恢复原数组**：利用前缀和的方法，通过 `a[i] = a[i - 1] + diff[i]` 恢复原数组。 4. **找出最大值**：使用 `*max_element` 函数找出数组中的最大值并输出。 ### 复杂度分析 - **时间复杂度**：$O(n + q)$，其中 `n` 是数组的长度，`q` 是操作的次数。 - **空间复杂度**：$O(n)$，主要用于存储原数组和差分数组。 ######[AI问答 | 751点数解答 | 2026-03-20 19:57:04]