逆序对统计：归并排序与树状数组解法详解

1. 从一道经典题说起：逆序对到底在解决什么问题

第一次接触 Ultra-QuickSort 这道题的人，多半会被它的名字骗到。题目叫“超级快排”，看起来像是让你手写一个快速排序，但真正读完题面就会发现，它问的根本不是排序本身，而是：把一个无序序列通过相邻元素交换变成有序序列，最少需要交换多少次。这个问题的答案，恰好就是序列中逆序对的总数。

我当年第一次做这道题的时候，老老实实写了个冒泡排序去数交换次数，结果数据规模一上来直接超时。后来才明白，这题的核心考点是逆序对的统计，而统计逆序对有两种主流做法：归并排序和树状数组（配合离散化）。这道题之所以经典，是因为它同时考察了算法选择、数据范围处理、以及边界细节，是一道非常适合用来打通“分治思想”和“树状数组应用”的题目。

这篇文章我会从零开始，把逆序对的概念、两种解法的原理、代码实现、以及实际踩过的坑全部讲清楚。不管你是刚学完排序的初学者，还是想复习树状数组的老手，都能从里面找到有用的东西。核心关键词就三个：逆序对、归并排序、树状数组，围绕它们展开的内容足够你彻底吃透这类问题。

先说说这题的实际意义。逆序对不只是一道算法题，它在很多场景里都有应用：比如衡量两个排列的“相似度”、计算序列的“混乱程度”、甚至在推荐系统里评估排序质量。理解了逆序对，你就掌握了一种把“无序程度”量化的工具。而 Ultra-QuickSort 这道题，就是把这个工具用最朴素的方式摆在你面前。

2. 逆序对的核心概念与问题拆解

2.1 什么是逆序对，为什么相邻交换次数等于逆序对数

逆序对的定义很直白：在一个序列中，如果存在两个位置 i 和 j，满足 i < j 但 a[i] > a[j]，那么 (i, j) 就构成一个逆序对。换句话说，前面的数比后面的数大，就是一对“逆序”。

那为什么“相邻交换变成有序”的最小次数等于逆序对数？这里有一个非常经典的证明思路。每次相邻交换，最多只能消除一个逆序对。因为交换的是相邻两个元素，只有这两个元素的相对顺序发生了变化，它们与其它元素之间的相对位置关系不变。如果这两个元素原本是逆序的（前大后小），交换后它们变成正序，逆序对总数减一；如果它们原本就是正序的，交换反而会增加一个逆序对，这显然不是最优操作。所以最优策略就是每次只交换相邻的逆序对，每交换一次消除一个逆序对，直到逆序对数为零。因此最少交换次数就等于初始逆序对的总数。

这个结论是整道题的理论基石。理解了它，你就知道题目本质上是在问你：这个序列里有多少个逆序对。

2.2 数据规模带来的挑战与算法选型

Ultra-QuickSort 这道题的数据规模通常给到 n 最大为 500000，元素值可能很大甚至为负数。如果用暴力双重循环去数逆序对，时间复杂度是 O(n²)，50万的数据量下运算次数达到 2.5×10¹¹ 级别，任何评测机都扛不住。所以必须选择 O(n log n) 的算法。

主流选择有两个：

• 归并排序法：在归并排序的合并过程中统计逆序对。归并排序本身就是分治，合并两个有序子数组时，如果右半部分的元素先于左半部分被取出，说明左半部分剩余的所有元素都比它大，这些就构成了逆序对。这个方法不需要额外处理数据范围，直接就能用。
• 树状数组法：把问题转化为“对于每个元素，统计它前面有多少个比它大的数”。用树状数组维护已经出现过的元素的计数，从后往前或从前往后遍历都可以。但树状数组的下标必须是整数且范围可控，如果元素值很大或是负数，就需要离散化。

两种方法各有优劣。归并排序写法固定，不容易出错，适合作为首选；树状数组代码更短，但离散化那一步容易出问题。我个人的建议是：如果时间紧张，优先写归并排序；如果想练树状数组，这题是绝佳的练习题。

2.3 离散化的必要性：为什么不能直接开数组

树状数组的本质是一个计数数组，下标对应元素的值。如果元素值范围是 -10⁹ 到 10⁹，你不可能开一个二十亿大小的数组。而且元素个数最多只有 50 万，大量数值空间是浪费的。离散化的思路就是：把原始值替换成它们在序列中的排名，排名范围就是 1 到 n，这样树状数组只需要开 n+1 的大小。

离散化的具体做法是：先把原数组复制一份，排序去重，然后用二分查找把每个原值映射成它的排名。注意，如果有重复元素，相同的值应该映射到相同的排名，这样才不会把相等的元素误判为逆序对。因为逆序对要求严格大于，相等的元素不构成逆序对。

提示：离散化时一定要去重。如果不去重，相同的值可能被映射成不同的排名，导致统计结果偏大。这是新手最容易踩的坑之一。

3. 归并排序法：分治思想统计逆序对

3.1 归并排序统计逆序对的原理

归并排序的核心是“分而治之”：把数组分成两半，分别排序，然后合并。在合并的过程中，我们可以顺便统计逆序对。具体来说，假设左半部分和右半部分都已经各自有序，我们用两个指针分别指向左半和右半的开头，比较两个指针指向的元素，把较小的那个放入临时数组。

关键点来了：当右半部分的元素小于左半部分的元素时，左半部分从当前指针到末尾的所有元素都比这个右半元素大。因为左半部分是有序的，当前左指针指向的元素已经是左半部分剩余元素中最小的了，它都比右半元素大，那它后面的元素肯定更大。所以此时逆序对数量增加“左半部分剩余元素个数”。

这个统计过程是精确的，不会重复也不会遗漏。每一对逆序对只会在它们被分到不同子数组、并且在合并时右半元素先被取出的那一刻被统计到。

3.2 归并排序的代码实现与细节注释

下面是我常用的归并排序统计逆序对模板，用 Python 写出来方便理解，实际比赛中可以用 C++ 获得更好的性能。

def merge_sort_count(arr, temp, left, right): if left >= right: return 0 mid = (left + right) // 2 count = 0 count += merge_sort_count(arr, temp, left, mid) count += merge_sort_count(arr, temp, mid + 1, right) i, j, k = left, mid + 1, left while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] count += mid - i + 1 j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for idx in range(left, right + 1): arr[idx] = temp[idx] return count

这段代码有几个细节值得注意。第一，arr[i] <= arr[j]用的是小于等于，而不是小于。为什么？因为当左右元素相等时，我们不应该把它算作逆序对。如果写成arr[i] < arr[j]，那么相等时就会走 else 分支，把右半元素先取出，导致逆序对数量多算。这是非常隐蔽的一个 bug。

第二，count += mid - i + 1这一句是核心。当右半元素 arr[j] 小于左半元素 arr[i] 时，左半部分从 i 到 mid 一共有mid - i + 1个元素，它们全都大于 arr[j]，所以一次性增加这么多逆序对。

第三，临时数组 temp 的复用。每次递归都新建数组会导致大量内存分配，影响性能。用一个全局或传入的 temp 数组，配合 left、right 下标来使用，是标准做法。

3.3 归并排序法的时间与空间复杂度分析

归并排序的时间复杂度是稳定的 O(n log n)。递归深度是 log n，每一层的合并操作总共处理 n 个元素，所以总操作数是 n log n。对于 n = 500000，log₂(500000) 约等于 19，总操作数大约 950 万次，完全可以在 1 秒内跑完。

空间复杂度是 O(n)，主要是临时数组的开销。递归调用栈的深度是 O(log n)，相比临时数组可以忽略。所以整体空间是 O(n)。

归并排序法最大的优势是不需要离散化，也不关心元素的值域范围。不管元素是整数、负数还是很大的数，只要能比较大小，就能统计逆序对。这让它在处理这类问题时非常省心。

注意：递归实现时，如果 n 特别大，比如上百万，递归深度虽然只有 log n 不会栈溢出，但函数调用开销会累积。如果追求极致性能，可以改写成迭代版的归并排序。不过对于 50 万的数据量，递归版完全够用。

4. 树状数组法：离散化加计数统计

4.1 树状数组的基本原理回顾

树状数组（Binary Indexed Tree，BIT）是一种支持单点更新和前缀查询的数据结构，两者都是 O(log n) 的时间复杂度。它的核心思想是利用二进制中最低位的 1 来划分管理区间。每个位置 i 管理的是从 i 往前数 lowbit(i) 个元素的和，其中 lowbit(i) = i & (-i)。

树状数组的代码极其简洁，两个核心操作：

def lowbit(x): return x & (-x) def update(bit, i, delta, n): while i <= n: bit[i] += delta i += lowbit(i) def query(bit, i): res = 0 while i > 0: res += bit[i] i -= lowbit(i) return res

update 是单点更新，把位置 i 的值增加 delta；query 是前缀查询，返回位置 1 到 i 的和。这两个操作是树状数组的全部。

4.2 用树状数组统计逆序对的思路

用树状数组统计逆序对，核心思路是：从后往前遍历数组，对于每个元素，查询当前树状数组中比它小的元素个数，这些元素都在它后面且比它小，所以构成逆序对。查询完后，把当前元素加入树状数组。

具体来说，假设我们已经离散化，元素值映射到 1 到 n。从后往前遍历，对于位置 i 的元素，它在树状数组中的排名是 rank。那么比它小的元素个数就是 query(bit, rank - 1)。因为树状数组里存的是已经遍历过的（也就是原数组中在它后面的）元素的出现情况。query(rank - 1) 返回的就是后面比它小的元素个数，这些元素与当前元素构成逆序对。

为什么是 rank - 1 而不是 rank？因为逆序对要求严格大于，相等的元素不算。查询比它小的，就是排名小于它的，即 rank - 1。

遍历完所有元素后，累加的 query 结果就是逆序对总数。

4.3 离散化的完整实现步骤

离散化是树状数组法的前置步骤，做不好这一步后面全错。我通常用这样的流程：

1. 复制原数组到 sorted_arr。
2. 对 sorted_arr 排序。
3. 对 sorted_arr 去重（用集合或手动去重）。
4. 对于原数组的每个元素，用二分查找在去重后的 sorted_arr 中找到它的位置，位置从 1 开始编号，这个编号就是它的排名。

def discretize(arr): sorted_unique = sorted(set(arr)) rank_map = {val: idx + 1 for idx, val in enumerate(sorted_unique)} return [rank_map[val] for val in arr]

用字典做映射比二分查找更快，因为字典查询是 O(1)。但字典会占用额外内存，如果内存紧张可以用二分。对于 50 万的数据量，字典完全没问题。

离散化后，所有元素的值都在 1 到 n 之间，树状数组开 n+1 大小即可。

4.4 树状数组法的完整代码与逐行解析

def count_inversions(arr): n = len(arr) ranks = discretize(arr) bit = [0] * (n + 1) count = 0 for i in range(n - 1, -1, -1): r = ranks[i] count += query(bit, r - 1) update(bit, r, 1, n) return count

逐行看：ranks = discretize(arr)完成离散化；bit = [0] * (n + 1)初始化树状数组；从n-1到0倒序遍历；query(bit, r - 1)查询比当前元素小的已出现元素个数；update(bit, r, 1, n)把当前元素加入树状数组。

这段代码的时间复杂度是 O(n log n)，离散化排序是 O(n log n)，遍历是 O(n log n)，总体 O(n log n)。空间复杂度是 O(n)，主要是 ranks 数组和 bit 数组。

提示：如果不想从后往前遍历，也可以从前往后遍历，但查询的逻辑要反过来：查询比当前元素大的元素个数，即 query(n) - query(rank)。两种方式等价，选自己习惯的就好。

5. 两种方法的对比与选型建议

5.1 性能对比与适用场景

从常数因子看，树状数组通常比归并排序快一些，因为它的操作更简单，没有递归开销。但归并排序胜在不需要离散化，省去了一步容易出错的预处理。

如果元素值范围本身就不大，比如都在 1 到 10⁵ 之间，那树状数组可以直接用，不需要离散化，这时候树状数组是最优选择。如果元素值范围很大或是负数，归并排序更省心。

5.2 我个人的选型经验

做了这么多逆序对的题，我的经验是：看数据范围和元素类型。如果题目明确说元素是 1 到 n 的排列，那树状数组直接上，代码短且快。如果元素值范围未知或很大，归并排序是稳妥选择。如果题目还要求输出排序后的序列或者有其他附加条件，归并排序可能更方便扩展。

另外，有些题目会卡常数，比如 n = 10⁶ 且时间限制很紧。这时候树状数组的优势就体现出来了。但 Ultra-QuickSort 这道题 n = 500000，两种方法都能过，选哪个看个人习惯。

注意：不管选哪种方法，都要用 64 位整数来存逆序对数量。n = 500000 时，逆序对最多可以达到 n(n-1)/2 ≈ 1.25×10¹¹，远超 32 位整数的范围。用 int 会溢出，必须用 long long。这是很多人 WA 的原因。

6. 实操中的常见问题与排查技巧

6.1 答案溢出：为什么结果总是负数

这是最经典的问题。逆序对最大数量是 n(n-1)/2，当 n = 500000 时约为 1.25×10¹¹，而 32 位有符号整数的最大值是 2.1×10⁹，远远不够。如果用了 int 类型，结果会溢出变成负数或错误值。

解决方法很简单：把所有涉及计数的变量都声明为 long long（C++）或直接用 Python（Python 的整数是任意精度的，不会溢出）。在 C++ 中，long long是 64 位的，最大约 9.2×10¹⁸，完全够用。

6.2 离散化错误：重复元素导致的统计偏差

如果离散化时没有去重，相同的值可能被映射成不同的排名。比如数组 [5, 5]，如果不去重，排序后还是 [5, 5]，第一个 5 映射到 1，第二个 5 映射到 2。这样在统计时，后面的 5 会被认为比前面的 5 小（因为排名 2 > 1，查询 rank-1=1 时会统计到前面的 5），导致多算逆序对。实际上两个 5 相等，不构成逆序对。

解决方法就是离散化前先去重。用sorted(set(arr))一步到位。

6.3 边界条件：n=0 或 n=1 的情况

虽然 Ultra-QuickSort 通常 n 至少为 1，但写代码时要考虑边界。n=0 或 n=1 时逆序对为 0，直接返回即可。归并排序的递归终止条件是left >= right，自然处理了这种情况。树状数组的循环range(n-1, -1, -1)在 n=0 时不会执行，也返回 0。

6.4 常见问题速查表

6.5 调试技巧：用小数据验证

写完代码后，不要急着提交。先用小数据手动验证。比如数组 [3, 1, 2]，逆序对有 (3,1) 和 (3,2)，共 2 个。用你的代码跑一下，看输出是不是 2。再试 [1, 2, 3] 输出 0，[3, 2, 1] 输出 3。这几个基本用例过了，再试有重复元素的，比如 [2, 2, 1]，逆序对只有 (2,1) 两次？不对，是第一个 2 和 1，第二个 2 和 1，共 2 个。验证一下。

如果小数据都对，大数据出错，那多半是溢出问题。如果小数据就错，那就是逻辑问题，重点检查离散化和归并的比较条件。

7. 从逆序对延伸出去：更多应用场景

逆序对不只是这一道题。在很多地方你都会遇到它的变体。比如“最少交换次数使数组有序”，如果允许交换任意两个元素，那最少次数是 n 减去循环节个数，这和逆序对无关；但如果只允许相邻交换，那就是逆序对数。再比如“判断一个排列的奇偶性”，排列的逆序对数的奇偶性决定了它是偶排列还是奇排列，这在群论和某些算法中很有用。

还有一个常见的变体是“三维偏序”问题，比如统计满足 a[i] < a[j] 且 b[i] < b[j] 且 c[i] < c[j] 的数对个数。这需要用 CDQ 分治或树套树，但核心思想还是逆序对的扩展。先把一维排序，然后对第二维用归并统计，第三维用树状数组。如果你能彻底理解二维逆序对，三维偏序就是自然的延伸。

在实际工程中，逆序对可以用来衡量两个排序结果的差异。比如两个推荐算法给出了不同的排序，你可以用逆序对数来量化它们的差异程度。逆序对越多，说明两个排序差异越大。这个指标在评估排序稳定性时很有用。

8. 一些实操心得与避坑建议

最后分享几个我在做这类题时总结的小技巧。第一，模板要背熟。归并排序统计逆序对和树状数组的代码应该练到闭着眼睛都能写出来，这样比赛时才能快速上手。第二，先想清楚再写。不要一上来就敲代码，先确定用哪种方法，离散化怎么做，边界怎么处理，想清楚了再动手，能省很多调试时间。第三，测试用例要全面。除了题目给的样例，自己造几组：全正序、全逆序、有重复、n=1、n=0，这些都能过基本就没问题了。

还有一个细节：如果题目是多组输入，记得每次都要清空树状数组和临时数组。我见过太多人因为忘记清空导致第二组数据出错。归并排序的临时数组如果开在全局，每次用之前不需要特别清空，因为会被覆盖；但树状数组必须重新初始化为 0。

关于输入输出，如果数据量大，用scanf/printf而不是cin/cout，或者加上ios::sync_with_stdio(false)加速。50 万的数据量，输入输出优化能省不少时间。

这个题后续还可以这样扩展：试着用 CDQ 分治解决三维偏序问题，或者用归并排序的思想解决“区间内逆序对个数”的查询问题。逆序对是一个入口，背后是一整套分治和数据结构的知识体系。把这道题吃透，后面很多题都会变得容易。