好的，作为排序算法领域的大神，我今天为你讲解一个尚未覆盖的经典题目。 归并排序中“小和问题”的高效求解 题目描述 给定一个整数数组 arr ，我们定义“小和”如下：数组中一个元素 arr[i] 左边比它小的所有元素之和，称为该元素的小和。数组的“总小和”定义为所有元素的小和之和。 例如，数组 arr = [1, 3, 4, 2, 5] 。 1 左边没有元素，小和为 0。 3 左边比它小的元素为 1，小和为 1。 4 左边比它小的元素为 1, 3，小和为 1 + 3 = 4。 2 左边比它小的元素为 1，小和为 1。 5 左边比它小的元素为 1, 3, 4, 2，小和为 1 + 3 + 4 + 2 = 10。 总小和 = 0 + 1 + 4 + 1 + 10 = 16。 要求设计一个时间复杂度优于 O(n²) 的算法，计算给定数组的总小和。 解题过程循序渐进讲解 步骤 1：暴力解法分析与问题转化 最直观的方法是遍历每个元素 arr[i] ，再遍历它左边所有的元素 arr[j] (j < i) ，如果 arr[j] < arr[i] ，则累加到小和中。这需要两层循环，时间复杂度为 O(n²)。 我们需要寻找更优的解法。注意“小和”的定义： 对于元素 arr[i] ，其小和是所有左边小于它的值的和 。 我们可以换一个视角： 对于任意一个数 arr[i] ，它对于其右边比它大的每一个数，都会贡献一次自身的值作为小和的一部分 。 让我们用例子验证这个视角： 数组 [1, 3, 4, 2, 5] 。 数字 1：右边比它大的数有 3, 4, 2, 5。所以 1 会对总小和贡献 1 * 4 = 4 。 数字 3：右边比它大的数有 4, 5。所以 3 会贡献 3 * 2 = 6 。 数字 4：右边比它大的数有 5。所以 4 会贡献 4 * 1 = 4 。 数字 2：右边比它大的数有 5。所以 2 会贡献 2 * 1 = 2 。 数字 5：右边没有数，贡献 0。 总贡献 = 4 + 6 + 4 + 2 + 0 = 16。结果正确！ 问题于是转化为： 如何高效地计算，对于数组中的每一个数，其右边有多少个数比它大？ 步骤 2：联想归并排序与逆序对 计算“右边有多少个数比它大”是 逆序对 问题（计算右边有多少个数比它小）的一个变体。逆序对问题可以利用归并排序的过程在 O(n log n) 时间内高效求解。这里的问题非常相似，我们同样可以利用归并排序的“分治”与“合并”过程。 在归并排序的合并（Merge）阶段，两个子数组（假设为左数组 L 和右数组 R ）都是有序的。当我们从左数组取出一个元素 L[i] 放入合并结果时，我们可以立刻知道这个 L[i] 比当前右数组 R 中还没有被处理的那些元素（即比 L[i] 大的元素）都要小 。 步骤 3：设计合并阶段的计算逻辑 假设我们在合并 [left, mid] 和 [mid+1, right] 两个有序区间。 我们使用两个指针 p1 和 p2 分别指向左区间和右区间的起始位置。 还有一个辅助数组 help 存放合并结果。 关键逻辑： 比较 arr[p1] 和 arr[p2] 。 如果 arr[p1] < arr[p2] ：这意味着左指针指向的数 arr[p1] 小于右指针指向的数 arr[p2] 。由于右区间是有序的，那么 arr[p2] 以及它之后的所有数（在右区间内）都一定大于 arr[p1] 。所以， arr[p1] 对于总小和的贡献是： arr[p1] * (右区间剩余元素的数量) 。 右区间剩余元素数量 = right - p2 + 1 。 计算贡献后，将 arr[p1] 放入 help 数组， p1++ 。 如果 arr[p1] >= arr[p2] ：此时 arr[p1] 不小于 arr[p2] ，无法产生小和贡献（题目要求严格小于）。我们只需将 arr[p2] 放入 help 数组， p2++ 。 这个逻辑在合并的每一步，都能准确地计算出左区间元素对总小和的贡献。 步骤 4：递归分治框架 我们使用标准的归并排序递归框架： 终止条件 ：当 left == right 时，一个元素的小和贡献为 0，返回。 分解 ：计算中点 mid = left + ((right - left) >> 1) 。 递归 ：分别计算左半区间 [left, mid] 和右半区间 [mid+1, right] 内部产生的小和，并让这两个区间各自有序。 合并与计算 ：调用合并函数，在合并两个有序子数组的过程中，计算 跨越左右区间的小和贡献 （即左区间元素对于右区间元素的贡献），并累加到总小和中。 返回总小和 ：总小和 = 左区间内部小和 + 右区间内部小和 + 跨越左右区间的小和。 步骤 5：举例推导（核心） 以 arr = [1, 3, 4, 2, 5] 为例，我们模拟算法过程。 初始调用： process(0, 4) 。 第一层递归： mid = 2 ，分为 [0,2] ( [1,3,4] ) 和 [3,4] ( [2,5] )。 先递归处理左半部分 process(0,2) 和右半部分 process(3,4) 。 处理左半部分 [0,2] ( [1,3,4] ): mid = 1 ，分为 [0,1] ( [1,3] ) 和 [2,2] ( [4] )。 处理 [0,1] : mid=0 ，分为 [0,0] ( [1] ) 和 [1,1] ( [3] )。 合并 [1] 和 [3] ：因为 1 < 3 ，所以贡献 1 * 1 (右区间元素数) = 1。合并后数组为 [1,3] 。 处理 [2,2] : 直接返回。 现在合并 [0,1] 的有序结果 [1,3] 和 [2,2] 的有序结果 [4] 。 比较 1 和 4 : 1<4 ，贡献 1 * 1 = 1。 p1++ 。 比较 3 和 4 : 3<4 ，贡献 3 * 1 = 3。 p1++ 。 左区间耗尽，拷贝右区间 [4] 。 本次合并跨越贡献 = 1+3 = 4。 左半部分 [0,2] 总小和 = 左内部(1) + 右内部(0) + 跨越贡献(4) = 5。（注意这只是 [1,3,4] 这个子数组内部的总小和） 处理右半部分 [3,4] ( [2,5] ): mid = 3 ，分为 [3,3] ( [2] ) 和 [4,4] ( [5] )。 合并 [2] 和 [5] ： 2<5 ，贡献 2*1=2 。 右半部分 [3,4] 总小和 = 0+0+2 = 2。 现在回到第一层，合并左右两个有序大区间： 左区间已排序为 [1,3,4] ，右区间已排序为 [2,5] 。 p1 指向 1 ， p2 指向 2 。比较： 1 < 2 。 贡献： 1 * (右区间剩余元素数 = 2) = 2。放入1， p1++ 。 p1 指向 3 ， p2 指向 2 。比较： 3 >= 2 。 无贡献。放入2， p2++ 。 p1 指向 3 ， p2 指向 5 。比较： 3 < 5 。 贡献： 3 * (右区间剩余元素数 = 1) = 3。放入3， p1++ 。 p1 指向 4 ， p2 指向 5 。比较： 4 < 5 。 贡献： 4 * (右区间剩余元素数 = 1) = 4。放入4， p1++ 。 左区间耗尽，拷贝右区间 [5] 。 本次合并跨越贡献 = 2 + 3 + 4 = 9。 最终总小和： 总小和 = 左区间内部小和(5) + 右区间内部小和(2) + 跨越左右区间贡献(9) = 16。结果正确。 步骤 6：时间复杂度与空间复杂度分析 时间复杂度 ：算法主体是归并排序，合并过程中我们只增加了常熟时间的计算（乘法和累加）。因此总时间复杂度为 O(n log n) 。 空间复杂度 ：和归并排序一样，需要一个与原始数组等大的辅助数组，因此空间复杂度为 O(n) 。 步骤 7：关键点总结 视角转换 ：将“求每个数左边比它小的数的和”，转化为“求每个数对其右边比它大的数的贡献”。 利用归并排序的性质 ：在合并两个有序子数组时，可以高效、不重复地计算出左子数组元素对右子数组元素的“跨越”贡献。 分治思想 ：总小和 = 左半部分内部小和 + 右半部分内部小和 + 跨越左右部分的小和。通过递归，我们完美地分解并解决了问题。 边界处理 ：在合并逻辑中，只有当 arr[p1] < arr[p2] 时才计算贡献，严格遵循“小于”的定义。 通过以上步骤，我们就利用归并排序高效地解决了“小和问题”。这个题目是理解归并排序在“分治统计”类问题上应用的绝佳范例。