1. 从一道“看起来很简单”的题说起如果你刷过一段时间的算法题一定遇到过这种题目给你一个数组让你求所有数对差的绝对值之和。第一次看到这类题很多人的第一反应是“这不就是两层循环暴力枚举吗”然后兴冲冲地写了个 O(N²) 的解法交上去结果屏幕上赫然出现一个 TLE超时。AtCoder Beginner Contest 186 的 D 题 “Sum of difference” 就是这样一个典型的“入门级陷阱题”——它的题意极其朴素但数据规模会逼着你必须想出 O(N log N) 甚至 O(N) 的做法。这道题的核心考点其实就两个排序和前缀和。听起来都是老生常谈的东西但真正在比赛环境下能不能快速反应过来、能不能把边界处理好就是另一回事了。我见过不少刚接触竞赛的朋友单独问他们“前缀和是什么”能答得头头是道但一放到具体题目里就想不到要用或者用的时候下标搞错、溢出没防住白白丢分。这篇文章我会把这道题从头到尾拆一遍题目到底在问什么、暴力为什么不行、排序在这里起了什么作用、前缀和是怎么把复杂度压下来的、代码怎么写才不会翻车以及我自己在做这类“数对求和”问题时总结出来的一套通用思路。不管你是刚入门算法竞赛的新手还是想复习一下基础技巧的老手应该都能从里面捞到点东西。整篇内容会围绕前缀和这个关键词展开但不会只讲前缀和本身而是讲它在真实题目里是怎么被“用起来”的。2. 题目到底在求什么把题意翻译成人话2.1 原始题意的拆解题目大意是这样的给你 N 个整数 A₁, A₂, …, A_N要求你计算所有满足 i j 的数对 (i, j) 的 |A_i − A_j| 之和。换句话说就是把数组里所有两两组合的差的绝对值全部加起来。用数学式子写出来就是求 Σ_{1 ≤ i j ≤ N} |A_i − A_j|这个式子里有几个关键信息需要拎清楚。第一是i j也就是每个数对只算一次不会重复计算 (i, j) 和 (j, i)。第二是绝对值这意味着不管谁大谁小差永远是正的。第三是所有数对也就是一共有 N(N−1)/2 个数对。N 的范围在这道题里可以到 2×10⁵ 这个量级。这个数字很关键它直接决定了你能用什么复杂度的算法。2×10⁵ 的平方是 4×10¹⁰这个数量级的操作在现代计算机上跑个几十秒甚至几分钟都正常而竞赛通常只给你 2 秒。所以 O(N²) 必死无疑必须想办法降到 O(N log N) 或 O(N)。2.2 为什么绝对值是个“麻烦”如果题目求的是 Σ(A_j − A_i) 且保证 i j 时 A_i ≤ A_j那事情就简单了直接前缀和一遍过。但问题是数组是无序的A_i 和 A_j 谁大谁小完全不确定绝对值符号让每一项的符号都变得不可预测。这就是这道题第一个“卡点”绝对值的存在让求和式无法直接线性展开。你必须想办法把绝对值去掉或者把数组变成“有序”的状态让大小关系变得确定。而“让大小关系确定”这件事恰好就是排序能干的活。所以这道题的第一步思路就呼之欲出了——先排序。2.3 一个具体的例子帮助理解拿题目给的样例来说假设数组是 [3, 1, 4]。所有数对是 (3,1)、(3,4)、(1,4)对应的差是 |3−1|2、|3−4|1、|1−4|3加起来是 6。如果我先把它排序成 [1, 3, 4]再算|1−3|2、|1−4|3、|3−4|1加起来还是 6。结果一样但排序之后有个巨大的好处——对于任意 i j都有 A_i ≤ A_j绝对值可以直接去掉变成 A_j − A_i。这一步转化是整道题的核心突破口后面所有的优化都建立在它之上。3. 暴力枚举为什么会超时算一笔账3.1 暴力解法的代码长什么样最直观的写法就是双重循环n int(input()) a list(map(int, input().split())) ans 0 for i in range(n): for j in range(i 1, n): ans abs(a[i] - a[j]) print(ans)这段代码逻辑上完全正确样例也能过。但它的时间复杂度是 O(N²)。当 N 2×10⁵ 时内层循环执行的总次数约为 N²/2 2×10¹⁰ 次。每次循环里还有一次 abs 运算和一次加法实际指令数更多。3.2 2×10¹⁰ 次操作意味着什么现代 CPU 每秒大概能执行 10⁸ 到 10⁹ 次简单操作取决于具体操作类型和语言。Python 这种解释型语言更慢每秒可能只有 10⁷ 到 10⁸ 次有效循环迭代。2×10¹⁰ 次迭代就算按每秒 10⁸ 次算也要 200 秒。而竞赛的时限通常是 2 秒。差了整整两个数量级。所以暴力解法不是“慢一点”而是“根本跑不完”。这就是为什么必须换思路。很多新手会想“我优化一下常数因子行不行”比如用更快的语言、减少函数调用。但常数优化最多带来几倍提升面对 100 倍的差距杯水车薪。必须从算法复杂度层面降维。3.3 从暴力到优化的思维跳跃暴力的本质是“枚举每一个数对单独计算它的贡献”。优化的方向通常有两个要么减少枚举的对象要么把“逐个计算”变成“批量计算”。前缀和属于后者。它的核心思想是如果我能快速求出“某个区间内所有元素的和”那我就不需要一个个去加了。放到这道题里排序之后对于每个位置 j它作为较大值出现在所有 i j 的数对中贡献是 A_j − A_i。把 j 固定对所有 i j 求和得到的就是 j × A_j − (A_1 A_2 … A_{j−1})。后面那个括号里的东西正好就是前缀和。4. 排序 前缀和把 O(N²) 压成 O(N log N)4.1 排序如何“消灭”绝对值前面已经提到排序之后数组单调不减对于 i j 恒有 A_i ≤ A_j于是 |A_i − A_j| A_j − A_i。这一步把带绝对值的非线性表达式变成了纯线性的减法是整个优化的地基。这里有个细节值得强调排序不会改变答案。因为原题求的是所有数对差的绝对值之和而“数对”本身是无序的集合概念你把数组重新排列数对的集合并没有变只是顺序变了。差的绝对值也不受顺序影响。所以排序是“无损变换”可以放心做。排序的复杂度是 O(N log N)对于 N 2×10⁵大约是 2×10⁵ × 18 ≈ 3.6×10⁶ 次比较操作完全在可接受范围内。4.2 固定右端点把求和拆开排序后我们考虑每一个位置 j从 0 开始计数它作为数对中较大的那个元素会和前面所有的 i j 组成数对。它对总答案的贡献是Σ_{i j} (A_j − A_i) j × A_j − Σ_{i j} A_i这里 j 既是下标也是“前面元素的个数”如果从 0 开始计数的话前面正好有 j 个元素。Σ_{i j} A_i 就是前 j 个元素的和也就是前缀和。于是整个答案就是ans Σ_{j0}^{N−1} (j × A_j − prefix[j])其中 prefix[j] A_0 A_1 … A_{j−1}prefix[0] 0。4.3 前缀和的递推计算前缀和不需要额外开一个数组可以在遍历过程中用一个变量滚动维护a.sort() ans 0 prefix 0 for j in range(n): ans j * a[j] - prefix prefix a[j] print(ans)这段代码的时间复杂度是 O(N log N)排序占主导空间复杂度 O(1)不算输入数组本身。相比暴力的 O(N²)这是质的飞跃。我用一个具体例子走一遍确保每一步都对得上。数组排序后是 [1, 3, 4]ja[j]prefix加之前贡献 j×a[j] − prefixans0100×1 − 0 001311×3 − 1 222442×4 − 4 46最终 ans 6和暴力结果一致。注意 j0 时贡献为 0因为第一个元素前面没有元素不构成任何数对这是符合预期的。5. 代码实现里的那些“坑”从能过样例到真正 AC5.1 数据范围与溢出问题这道题 N 最大 2×10⁵A_i 的范围在题目里通常给到 10⁸ 或 10⁹ 量级。我们来估算一下答案的最大值。最坏情况下所有数对差的绝对值都接近 10⁹数对数量约 N²/2 2×10¹⁰乘起来是 2×10¹⁹。这个数字已经超过了 64 位有符号整数的上限约 9.2×10¹⁸。等等这里要小心。实际上 A_i 的具体范围决定了会不会溢出。如果 A_i ≤ 10⁸那么最大差约 10⁸答案上限约 2×10¹⁰ × 10⁸ 2×10¹⁸刚好在 64 位整数范围内9.2×10¹⁸。但如果 A_i 到 10⁹就会溢出。在 Python 里这不是问题因为 Python 的整数是任意精度的。但在 C 里你必须用long long而且中间计算j * a[j]时也要确保是 long long 运算否则int * int会先溢出再赋值。这是个非常经典的翻车点。// C 正确写法 long long ans 0, prefix 0; for (int j 0; j n; j) { ans 1LL * j * a[j] - prefix; // 1LL 强制提升为 long long prefix a[j]; }那个1LL *是必须的。我见过太多人因为漏了这个在本地小数据上跑得好好的一交上去就 WA答案错误查半天查不出来。5.2 下标从 0 还是从 1 开始前缀和这类题目下标从 0 开始还是从 1 开始很容易把人绕晕。我的建议是统一用 0 开始然后在推导时把“前面有几个元素”和“下标”对应清楚。从 0 开始计数时位置 j 前面正好有 j 个元素下标 0 到 j−1所以系数就是 j。如果从 1 开始计数位置 j 前面有 j−1 个元素系数变成 j−1prefix 的含义也要相应调整。两种都能做但混用必错。我个人的习惯是读入数组后用 0-based排序后用 0-based循环变量 j 从 0 到 n−1系数直接用 j。这样最不容易出错因为“下标”和“前面元素个数”在 0-based 下天然相等。5.3 排序的方向与稳定性这道题只需要升序排序。Python 的list.sort()和 C 的std::sort默认都是升序直接用就行。不需要考虑稳定性因为相等的元素之间差为 0谁前谁后不影响结果。但有一个小细节如果数组里有重复元素排序后它们相邻差为 0贡献也是 0逻辑上完全没问题。不需要去重去重反而会改变数对的数量导致答案错误。这一点新手容易想当然。5.4 输入规模大时的读取效率N 到 2×10⁵ 时输入本身就有 2×10⁵ 个数字。在 Python 里用input()逐行读或者sys.stdin.readline()都可以但如果用input()且数据量再大一点可能会成为瓶颈。稳妥的做法是用sys.stdin.read().split()一次性读完再解析。import sys def main(): data sys.stdin.read().split() n int(data[0]) a list(map(int, data[1:1n])) a.sort() ans 0 prefix 0 for j in range(n): ans j * a[j] - prefix prefix a[j] print(ans) main()这种写法在 AtCoder 上是很常见的模板读入速度快不容易因为 IO 拖后腿。6. 举一反三这类“数对求和”问题的通用套路6.1 识别题型特征这类题通常有几个共同特征求所有数对或所有子区间的某种函数值之和、数据规模大到 O(N²) 过不了、函数值里带绝对值或者 max/min 这种“分段”性质。一旦看到这些信号就应该条件反射地想到“排序 前缀和”或者“排序 双指针”。核心逻辑是排序把无序变有序有序之后分段性质变成确定的线性关系前缀和把逐个累加变成批量查询。这三步组合起来能把很多看似 O(N²) 的问题降到 O(N log N)。6.2 一个变体求所有数对的最大值之和假设题目改成求 Σ_{ij} max(A_i, A_j)。排序后对于位置 j它作为最大值的条件是 i j贡献是 A_j 乘以“前面元素的个数”即 j。所以答案就是 Σ j × A_j。这个更简单连前缀和都不需要。再比如求 Σ_{ij} min(A_i, A_j)。排序后位置 i 作为最小值和它配对的是所有 j i贡献是 A_i × (N−1−i)。答案就是 Σ A_i × (N−1−i)。同样不需要前缀和。而本题求的是差的绝对值等价于“大减小”所以需要同时知道“较大值”和“前面所有较小值的和”这才用上了前缀和。理解了这个层次你就能根据具体函数形式判断需不需要前缀和。6.3 另一个变体带模数的版本有些题目会要求答案对某个大质数取模。这时候前缀和依然能用但要注意每一步都取模防止中间结果过大。Python 里无所谓C 里要小心ans (ans ...) % MOD的写法以及减法出现负数时加 MOD 再取模。const long long MOD 1e9 7; ans (ans (1LL * j * a[j] % MOD - prefix MOD) % MOD) % MOD; prefix (prefix a[j]) % MOD;那个 MOD是为了防止减法结果为负。这是取模运算的经典技巧值得记牢。6.4 复杂度分析的通用方法判断一个解法能不能过关键是估算操作次数。经验法则是1 秒时限下C 大约能跑 10⁸ 次简单操作Python 大约 10⁷ 次。所以看到 N 2×10⁵O(N²) 是 4×10¹⁰必死O(N log N) 是 3.6×10⁶轻松过O(N) 是 2×10⁵更是毫无压力。养成看数据范围反推复杂度的习惯能让你在比赛中少走很多弯路。很多人不是不会写优化算法而是压根没意识到需要优化看到题就开始暴力写完才发现过不了时间也浪费了。7. 我在实战中总结的几条经验第一先想清楚再动手。这道题如果上来就写暴力可能五分钟就写完了但交上去 TLE 之后还得重新想反而更慢。花两分钟分析数据范围、判断需要什么复杂度、想清楚排序和前缀和的逻辑再动手写总时间反而更短。第二排序是很多问题的“第一把钥匙”。当你面对一个涉及大小关系、绝对值、max/min 的问题且数据无序时先试试排序。排序之后很多性质会变得简单这是竞赛里非常高频的技巧。第三前缀和要理解成“批量查询区间和”的工具而不是死记公式。这道题里前缀和的本质是“快速得到前面所有元素的和”从而避免内层循环。理解了这个本质你就能在别的题里灵活运用而不是只会套这一道题的模板。第四注意整数溢出和下标边界。这两类错误在竞赛里极其常见而且往往在小数据上测不出来。写完代码后用最大数据范围心算一下中间结果看看会不会溢出用最小数据N1、N2手动跑一遍看看下标有没有越界。第五多写几组对拍。如果时间允许写一个暴力版本和一个优化版本随机生成小数据对拍能快速发现逻辑错误。这是提升正确率最有效的手段之一比盯着代码看半天强得多。这道题本身不难但它把排序、前缀和、复杂度分析、边界处理这几个基础功都串起来了是一道很好的练手题。把它的每个细节都吃透比刷十道同类型的题更有价值。