别再暴力循环了！蓝桥杯LQ0014这道‘求和’题，用前缀和5行代码就能搞定

蓝桥杯LQ0014求和题从暴力破解到前缀和的思维跃迁在算法竞赛的征途中我们常常会遇到看似简单却暗藏玄机的题目。蓝桥杯LQ0014求和题正是这样一个典型案例——它表面上要求计算两两相乘再相加的和实则考察选手对算法优化的深刻理解。本文将带你从最朴素的暴力解法出发逐步揭示前缀和这一神奇工具如何将时间复杂度从O(n²)降至O(n)同时对比公式法的精妙之处让你真正掌握思维转换这一算法竞赛的核心能力。1. 问题本质与暴力解法剖析题目要求计算给定n个整数a[1],a[2],...,a[n]的两两乘积之和即S a[1]·a[2] a[1]·a[3] ... a[n-1]·a[n]。最直观的解法莫过于暴力枚举所有可能的数对long long sum 0; for (int i 0; i n; i) for (int j i 1; j n; j) sum a[i] * a[j];这种解法虽然简单直接但当n达到2×10⁵时其时间复杂度O(n²)将导致无法接受的性能问题。以现代CPU每秒约10⁹次运算的能力计算n2×10⁵时所需时间约为(2×10⁵)²/10⁹40秒远超竞赛允许的时间限制。暴力解法的三个致命缺陷重复计算每个乘积项被独立计算忽略了数值间的内在关联缓存不友好双重循环导致内存访问模式效率低下无法利用数学性质没有发掘输入数据的潜在规律2. 前缀和化繁为简的思维转换前缀和的核心思想是通过预处理构建一个辅助数组使得任意区间的和可以在常数时间内获得。对于本题我们可以将原始问题重新表述S a₁(a₂a₃...aₙ) a₂(a₃...aₙ) ... aₙ₋₁aₙ观察发现每个括号内的求和都可以表示为前缀和的差值。定义前缀和数组prefix其中prefix[i] a₁ a₂ ... aᵢ则有S a₁×(prefix[n]-prefix[1]) a₂×(prefix[n]-prefix[2]) ... aₙ₋₁×(prefix[n]-prefix[n-1])但更精妙的是我们可以在线计算前缀和无需存储整个数组long long sum 0, psum 0; for (int i 1; i n; i) { scanf(%d, a); sum psum * a; // 当前数与之前所有数的乘积和 psum a; // 更新前缀和 }前缀和解法的优势分析特性暴力解法前缀和解法时间复杂度O(n²)O(n)空间复杂度O(n)O(1)代码复杂度简单中等适用数据规模n≤10⁴n≤10⁶3. 公式法数学洞察力的极致体现除了前缀和我们还可以通过数学公式直接求解。考虑所有数之和的平方(sum)² (a₁ a₂ ... aₙ)² a₁² a₂² ... aₙ² 2S因此所求S可以表示为S [(sum)² - sum_of_squares] / 2实现代码如下long long sum 0, sum1 0; for (int i 1; i n; i) { scanf(%d, a); sum a; sum1 a * a; } printf(%lld\n, (sum * sum - sum1) / 2);公式法与前缀和法的对比时间复杂度两者均为O(n)单次遍历空间复杂度均为O(1)无需额外存储数值稳定性前缀和法psum*a可能导致中间结果溢出公式法sum*sum极易溢出需确保使用足够大的数据类型适用性前缀和法更通用可扩展至其他类似问题公式法特定于此问题形式但更简洁4. 实战训练与思维拓展要真正掌握这类优化技巧仅理解原理远远不够。建议通过以下步骤进行刻意练习分阶段训练计划基础理解阶段手工计算小规模样例如n4比较暴力、前缀和、公式三种解法的中间结果代码实现阶段独立实现三种解法使用测试数据验证正确性测试大规模数据下的性能差异变式训练阶段修改问题为求三三乘积之和考虑带权重的两两乘积和处理模运算下的类似问题常见错误与调试技巧数据类型溢出// 错误示例 int sum 0; // 对于大n会溢出 // 正确做法 long long sum 0;边界条件处理空输入或单元素输入虽然题目保证n≥2极端值测试如所有a[i]1000n2×10⁵输入输出效率// 对于大规模数据使用更快的输入方式 scanf(%d, n); // 比cin更快5. 从特殊到一般的思维迁移前缀和技巧的应用远不止于此题。掌握这种思维模式后你可以解决更多类似问题前缀和的应用场景区间求和问题如子数组和等于k的个数统计满足特定条件的区间数量数据预处理加速后续查询思维迁移训练题给定数组求所有子数组的和的总和统计满足子数组平均值大于阈值的区间数量处理环形数组的相关问题在算法竞赛中真正的能力不在于记忆大量模板代码而在于这种将复杂问题逐步分解、寻找内在规律、最终用简洁高效的方式解决的思维能力。前缀和正是这种思维的一个典型代表——它教会我们有时候换个角度看问题计算复杂度就能从平方级降至线性级。