优化代码解决超时问题：双重和式计算的高效实现

原代码的时间复杂度是 $O(T \times (r - l)^2)$，当数据规模较大时，会出现超时（TLE）问题。可以通过数学推导优化算法，减少不必要的重复计算，将时间复杂度优化到 $O(T + n)$。 ### 优化思路 对于给定的区间 $[l, r]$，双重和式 $\sum_{i = l}^{r - 1}\sum_{j = i + 1}^{r - 1}(a[i]+a[j])$ 可以进行如下推导： 1. 先将和式展开： - $\sum_{i = l}^{r - 1}\sum_{j = i + 1}^{r - 1}(a[i]+a[j])=\sum_{i = l}^{r - 1}\left((r - i - 1)a[i]+\sum_{j = i + 1}^{r - 1}a[j]\right)$ 2. 为了快速计算 $\sum_{j = i + 1}^{r - 1}a[j]$，可以使用前缀和数组 $prefixSum$，其中 $prefixSum[k]=\sum_{i = 0}^{k - 1}a[i]$。那么 $\sum_{j = i + 1}^{r - 1}a[j]=prefixSum[r]-prefixSum[i + 1]$。 ### 优化后的代码 ```cpp #include <iostream> #include <vector> const int MOD = 10007; // 计算双重和式的值 int calculateSum(const std::vector<int>& a, const std::vector<int>& prefixSum, int l, int r) { int result = 0; for (int i = l - 1; i < r - 1; ++i) { // 计算 (r - i - 1) * a[i] result = (result + (long long)(r - i - 1) * a[i]) % MOD; // 计算 sum_{j = i + 1}^{r - 1} a[j] result = (result + prefixSum[r] - prefixSum[i + 1]) % MOD; if (result < 0) { result += MOD; } } return result; } int main() { int n, T; std::cin >> n >> T; std::vector<int> a(n); std::vector<int> prefixSum(n + 1, 0); // 读取数组元素并计算前缀和 for (int i = 0; i < n; ++i) { std::cin >> a[i]; prefixSum[i + 1] = (prefixSum[i] + a[i]) % MOD; } for (int t = 0; t < T; ++t) { int l, r; std::cin >> l >> r; // 计算并输出结果 std::cout << calculateSum(a, prefixSum, l, r) << std::endl; } return 0; } ``` ### 代码解释 1. **前缀和数组 `prefixSum`**：用于快速计算区间和。`prefixSum[k]` 表示数组 `a` 中前 `k` 个元素的和。 2. **`calculateSum` 函数**：根据推导的公式计算双重和式的值。 3. **`main` 函数**：读取输入，计算前缀和，处理每个查询并输出结果。 ### 复杂度分析 - **时间复杂度**：$O(T + n)$，其中 $n$ 是数组的长度，$T$ 是查询的次数。 - **空间复杂度**：$O(n)$，主要用于存储前缀和数组。 ######[AI问答 | 873点数解答 | 2026-05-01 15:51:01]