如果你第一次接触逆序对这个概念，可能会觉得这不过又是一个“两层循环就能数完”的数组小问题。真正写过的人才知道，当数组规模来到几十万甚至上百万时，暴力解法根本活不过评测样例。而“逆序对”这三个字一旦和“归并”绑定在一起，就成了一道非常经典的分治应用题：一边排序，一边把答案数出来，复杂度稳定在 O(n log n)。这篇文章我打算把这个过程彻底拆开讲，从定义、暴力解，到归并原理、三种语言实现，再到边界细节、树状数组方案和排查经验，把这道题变成你能随时复用的一套“肌肉记忆”。
1. 什么是逆序对：定义、暴力解与真正的需求
1.1 逆序对的定义，用一个例子讲明白
假设现在有一个数组 [3, 1, 2]。按逆序对的定义，所有满足“前面的数比后面的数大”的位置组合都算：3 和 1 是一对，因为 3 在 1 前面且 3 > 1；3 和 2 也是一对；但 1 和 2 不是，因为 1 < 2。所以这个数组的逆序对数量是 2。如果把数组改成 [1, 2, 3]，逆序对是 0，因为整个数组已经严格升序；如果改成 [3, 2, 1]，那么每一对前面的数都比后面的数大，总共就是 3 对。
这里有两个容易被忽略的细节。第一，逆序对要求的是a[i] > a[j]，是严格大于，不是大于等于。比如 [2, 2] 这个数组，两个 2 相等，它们的逆序对数量就是 0。很多人在写代码时用的是<判断而不是<=，结果把相等元素也当逆序对算了，这是最常见的错误之一。第二，下标组合 (i, j) 是有方向的，只统计满足 i < j 的组合，所以逆序对数量不会因为遍历顺序不同而改变。
逆序对数量其实可以理解成一组数据的“乱序程度”：0 代表完全有序，最大是 n(n-1)/2，代表完全倒序。在很多业务场景里，这个值可以用来衡量某种序列的稳定性，比如交易流水是否和预期顺序一致，或者两个有序状态之间的差异大小。算法题里它更常见，面试官经常会让你“用 O(n log n) 的时间求出一组数里的逆序对个数”，考察的就是你对归并排序、树状数组这类分治或前缀和思想的掌握程度。对准备面试的人来说，这题几乎是必背的模板题之一。
1.2 暴力写法：两分钟想完，但只能处理小数据
如果把逆序对定义直接翻译成代码，就是两层循环：外层枚举每个位置 i，内层枚举 i 后面的每个位置 j，只要 a[i] > a[j] 就计数。如下：
long long countInversionsBrute(const vector<int>& arr) { int n = arr.size(); long long ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { ans++; } } } return ans; }这段代码的正确性毋庸置疑，任何一个数组拿过来，跑一遍结果都对。但问题也很明显：复杂度是 O(n^2)。当 n 是 10^5 时，最坏情况要比较约 50 亿次，在普通机器上跑几十秒甚至几分钟都不奇怪，更别说 n 到 10^6 的情况了。这也是为什么几乎所有讲逆序对的资料都会直接跳过暴力解，直奔归并或者树状数组。
有人可能想，能不能先排序再统计？排序本身确实能让数组变成有序状态，但同时也破坏了元素之间原来的相对位置，而逆序对统计恰恰依赖这些相对位置。也就是说，简单排序解决不了这个问题，必须在“保留或利用元素相对顺序”的前提下，一边排序一边把逆序对数算出来。归并排序就是这类办法里最优雅的一种，甚至在很多代码库里，逆序对统计就是归并排序的一个额外副产品。
1.3 为什么这个问题值得单独研究
逆序对问题看起来只是一个计数题，但它牵扯到了几个很核心的能力。第一个是分治思想：把大数组分成左右两半，分别处理，再在合并时用 O(n) 时间把交叉产生的逆序对一次算清。第二个是复杂度的直觉：很多人能写出暴力解，却不清楚 O(n log n) 是怎么从“每次合并只数跨区间的逆序对”里得来的。第三个是细节敏感度：递归边界、相等判断、计数公式的区间长度，一个地方写错结果就完全不对，排查起来还特别隐蔽。
所以这道题在面试和竞赛中的地位都很高。面试中它考察的不光是你会不会背归并排序模板，更看重你能不能解释清楚“为什么右区间当前元素小于左区间当前元素时，逆序对数量是 mid-i+1”。竞赛中它则是分治和数据结构两个方向的基础题，掌握归并写法之后，再看树状数组解法就会顺很多。这篇文章后面所有内容，都是为了把这条能力链串起来，让你既能写出能跑的代码，又能真正理解背后的计数逻辑。
2. 用归并排序数逆序对：原理拆解
2.1 先复习归并排序的核心流程
归并排序的处理对象是一个数组，流程可以概括成三步：分、治、合。第一步“分”，把当前区间 [l, r] 从中间位置一分为二，变成 [l, mid] 和 [mid+1, r]；第二步“治”，递归地对左右两个子区间分别做归并排序，让它们各自变成有序序列；第三步“合”，把两个已经有序的子区间交错合并成一个更大的有序区间。
合并的操作很像整理两堆扑克牌：两堆牌各自按从小到大排好了，现在要合成一堆。每次只看两堆最顶上那张，谁小谁就先放到结果堆里。这个过程的复杂度是 O(n)，因为每张牌只被比较和移动一次。整个归并排序的复杂度 T(n)=2T(n/2)+O(n)，解出来就是 O(n log n)。
看起来这个排序过程和逆序对没什么直接关系，但关键就在合并这一步：合并两个有序子区间时，我们天然知道左边区间里的元素在原数组中全部位于右边区间元素之前。也就是说，如果发现左边当前的某个元素比右边当前元素大，那么左边当前元素后面的所有元素，也都比右边当前元素大，而且都位于它前面。这些组合，全部都是逆序对。这个洞察是整个算法的灵魂。
2.2 逆序对被“数”出来的关键瞬间
假设当前正在合并左区间 [l, mid] 和右区间 [mid+1, r]，用两个指针 i 和 j 分别指向两个区间中还没放置的最小元素。正常情况下，如果 a[i] <= a[j]，把 a[i] 放进临时数组即可，不产生逆序对；但如果 a[i] > a[j]，意味着右边的 a[j] 比左边的 a[i] 小，应该先放 a[j]。
从逆序对的角度看这个瞬间：a[j] 本来在原数组中位于 a[i] 的后面，但它比 a[i] 小，所以 (i, j) 是一个逆序对。更重要的是，由于左区间已经从小到大排好序，a[i] 后面的那些元素只会更大，所以从 i 到 mid 的每一个左区间元素，都会和 a[j] 构成逆序对。因此，一次合并操作至少可以数出 mid - i + 1 个逆序对，这个数量直接累加到答案里。
这个过程最妙的地方在于：它把“跨左右两个区间的逆序对”在一次合并中全部数完，而且不重不漏。至于完全在左区间内部、完全在右区间内部的逆序对，早就在递归处理子区间时算过了。每一层的合并只会处理“分界线两侧”的逆序对，合起来就是全部答案。这正是归并算法与逆序对问题结合得如此紧密的根本原因。
2.3 计数公式 mid - i + 1 是怎么来的
这里我把公式单独拿出来讲，因为很多代码你看得懂，但真到面试让你推导，容易卡壳。在一个递归层面对应区间 [l, r]，mid 是它的中点，左区间是 [l, mid]，右区间是 [mid+1, r]。合并时，i 是左区间的当前指针，j 是右区间的当前指针。
如果当前判定为 a[i] > a[j]，我们要回答的问题是：在这次合并中，和 a[j] 配对的逆序对有哪些？这些配对必须满足：左区间里的某个数在位置上位于 a[j] 前面，在值上比 a[j] 大。左区间中大于 a[j] 的起始位置就是 i，从 i 一直到 mid 全部满足条件，数量就是 mid - i + 1。这里不用数 j 右边还有什么，因为与左区间元素的配对会在后续迭代中由新的 j 指针完成，每次只处理当前右区间第一个未被合并的元素，保证不重不漏。
另一个小细节是：mid 最好用 l + (r - l) / 2 来算，而不是 (l + r) / 2。虽然很多题目的区间范围并不会让 l + r 溢出 int，但在极端数据下这是一个隐患，也是我建议大家养成的统一习惯。类似的边界细节在后面还会反复出现。
2.4 复杂度、稳定性和整体思路小结
空间方面，归并排序需要一个临时数组来存放合并结果，因此额外空间是 O(n)。时间方面，每一层合并总共处理 n 个元素，一共有 log2 n 层，所以总时间是 O(n log n)。这也是逆序对问题在面试中能拿高分的核心原因：同样的功能，暴力需要 O(n^2)，而归并只需要 O(n log n)，差距相当明显。
另外需要提一下稳定性。归并排序本身是稳定排序，也就是说相等元素的相对位置不会改变。我们用<=把左区间元素先放入临时数组，这个选择同时保证了“相等元素不构成逆序对”的语义。如果你把判断写成<，稳定性虽然不直接影响结果，但会把相等元素误判成逆序对，导致答案偏大。这里强烈建议把<=的语义记牢，不要在细节上翻车。
3. 完整代码实现：C++、Python、Java 三版
3.1 C++ 版本：最常用，逐行注释
C++ 里我习惯用 vector 存数组，因为动态数组的长度管理、初始化和传参都比裸数组省心。关键函数是 mergeCount，它既是排序函数，也是统计函数。递归边界是 l >= r，说明当前区间只有 0 个或 1 个元素，没有逆序对，直接返回 0。
#include <bits/stdc++.h> using namespace std; using ll = long long; ll mergeCount(vector<int>& arr, int l, int r) { if (l >= r) return 0; int mid = l + (r - l) / 2; ll ans = mergeCount(arr, l, mid); ans += mergeCount(arr, mid + 1, r); vector<int> tmp(r - l + 1); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { ans += mid - i + 1; // 关键计数 tmp[k++] = arr[j++]; } } while (i <= mid) tmp[k++] = arr[i++]; while (j <= r) tmp[k++] = arr[j++]; for (int p = 0; p < tmp.size(); p++) { arr[l + p] = tmp[p]; } return ans; } int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) cin >> arr[i]; cout << mergeCount(arr, 0, n - 1) << endl; return 0; }这段代码的运行流程是：先递归处理左右两半，分别拿到左半区间和右半区间内部的逆序对数；然后进入合并，用 while 循环同时扫描左右区间。当右边元素更小时，说明左区间当前指针到 mid 的所有元素都和这个右边元素构成逆序对，于是把 mid - i + 1 累加进 ans，同时把右边元素放入 tmp。最终，tmp 里是有序的合并结果，再写回 arr 的对应位置。整个过程结束后，arr 本身已经变成升序，但没关系，因为答案已经保存在返回值里了。
3.2 Python 版本：简洁写法
Python 里最容易理解的方式是直接基于切片递归。每次把数组从中间切成 left 和 right 两段，分别递归，然后合并。合并时同样用两个指针，如果左边当前元素小于等于右边，放左边；否则计数加上 len(left) - i，再放右边。
def inversion_count(nums): if len(nums) <= 1: return 0 mid = len(nums) // 2 left = nums[:mid] right = nums[mid:] cnt = inversion_count(left) + inversion_count(right) i = j = 0 merged = [] while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: cnt += len(left) - i merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) nums[:] = merged return cnt这个版本的优势是读起来很顺，几乎和思路一一对应。代价是每次递归都会创建 left、right 和 merged 三个新列表，空间占用比 C++ 版本高一些，所以在 Python 里处理 100 万级别的数据时会有明显的内存压力。如果只是平时练习、应付中等规模数据，这个写法完全够用；如果上了真正的海量数据，再用 C++ 或者 Python 的原地归并变体会更稳妥。另外，Python 的切片写法让代码显得特别清晰，面试时用来讲思路非常合适。
3.3 Java 版本：全局计数变量
Java 写递归时，我比较喜欢用一个 static 的全局变量来累计逆序对数，这样排序函数只需要负责分治和合并，不需要在每次递归中传递并返回 long 值。下面的实现里，mergeSort 没有返回值，所有计数都加在 ans 上。
import java.util.*; public class InversionCount { static long ans = 0; public static void mergeSort(int[] arr, int l, int r) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); int[] tmp = new int[r - l + 1]; int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { ans += mid - i + 1; tmp[k++] = arr[j++]; } } while (i <= mid) tmp[k++] = arr[i++]; while (j <= r) tmp[k++] = arr[j++]; System.arraycopy(tmp, 0, arr, l, tmp.length); } public static void main(String[] args) { int[] arr = {3, 1, 2}; mergeSort(arr, 0, arr.length - 1); System.out.println(ans); } }Java 的 System.arraycopy 效率比手写 for 循环略好，所以在最后回写数组时我用它。要注意的是，如果使用全局变量，在同一个程序里多次调用 mergeSort 之前必须把 ans 清零，否则上一次的结果会残留。这一点在写单元测试或者批处理多个样例时尤其容易踩到。
3.4 主函数与输入输出样例
我来给一个完整的使用示例。假设输入是：
5 3 2 1 4 5数组 [3, 2, 1, 4, 5] 里，逆序对是 (3,2)、(3,1)、(2,1)，一共 3 个，所以程序应该输出 3。你可以在本地把这段代码跑起来，然后换着输入验证。我一般会再跑这些边界样例：空数组（n=0）、单元素、完全升序、完全降序、全部相同元素。这些样例都不需要很多数据，却能快速暴露递归边界和相等判断的问题。
4. 边界条件与细节避坑：看似简单其实很容易翻车
4.1 统计结果用 int 一定会出事
这是逆序对问题里最常见的坑之一。最坏情况下，一个长度为 n 的完全逆序数组，逆序对数量是 n(n-1)/2。当 n 等于 10^5 时，这个值大约是 5 乘以 10 的 9 次方，已经超过了 32 位 int 能表示的最大值约 21 亿。如果按照题目常见的 n 范围 10^5 到 10^6，甚至 10^7，用 int 存结果，轻则变成负数，重则在累加过程中就出现溢出。
所以无论是 C++ 还是 Java，我都建议用 long long 或 long 来保存结果。Java 里 long 是 64 位有符号，在 n=10^6 时最大答案约 5 乘以 10 的 11 次方，完全够用。Python 则不用担心，它的整数是动态扩容的。这个改动只需要花一秒钟，但很多看起来“明明是对拍过的代码”一到大数据就出错，往往就是这种细节在拖后腿。
4.2 相等元素的处理：关键判断是 <= 还是 <
前面已经提到，逆序对的定义是严格大于，所以两个元素相等时不构成逆序对。在合并代码里，当 arr[i] == arr[j] 时，正确的做法是把左边元素放入临时数组，继续移动 i，而不是把右边元素放进去。如果用<作为“左边小于右边才放左边”的条件，那么相等时就会走“右边更小”的分支，执行 ans += mid - i + 1，把一组不相等的元素错算成逆序对。
举个例子：[1, 1] 只有两个相等元素，正确答案是 0。如果你把判断写成 if (a[i] < a[j]) 放左边，else 计数放右边，那么合并时会计数 1 个逆序对，完全错误。所以标准写法一定要是if (arr[i] <= arr[j])。这种问题在代码 review 时特别隐蔽，因为从纯排序逻辑看，<也能完成排序，只有在统计逆序对时才会暴露错误。
4.3 临时数组的开辟与回收
每个递归层都新建一个临时数组，逻辑是对的，但在 C++ 大数据量下会有不小的分配开销。如果是竞赛评测，n 到 10^6 级别时，递归调用会很多，频繁分配 vector 可能拖慢速度甚至导致内存碎片。更稳妥的做法是在递归函数外用 vector 预分配一个长度为 n 的全局临时数组，合并时用左边界 l 作为写回起点，运行过程始终复用这一块内存。
vector<int> tmpArr; void merge(vector<int>& arr, int l, int mid, int r) { int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (arr[i] <= arr[j]) tmpArr[k++] = arr[i++]; else { ans += mid - i + 1; tmpArr[k++] = arr[j++]; } } while (i <= mid) tmpArr[k++] = arr[i++]; while (j <= r) tmpArr[k++] = arr[j++]; for (int p = l; p <= r; p++) arr[p] = tmpArr[p]; }这里的 k 从 l 开始而不是从 0 开始，是为了让临时数组和原数组的区间下标一一对应，写回时直接读 tmpArr[p] 即可。这个优化不改变复杂度，但能明显减少常数开销。我个人的工程习惯是默认用这种写法，不仅在逆序对题里，在写其他归并类算法时也一样。
4.4 必测的几组数据
写完之后一定要先跑这些样例：空数组返回 0；长度为 1 如 [7] 返回 0；完全升序 [1,2,3,4,5] 返回 0；完全降序 [5,4,3,2,1] 返回 10；全部相同 [2,2,2,2] 返回 0；有正有负 [4,-1,2,-3,0] 返回多少，可以自己手算确认。为什么强调手算确认？因为逆序对题目看起来简单，但一旦结果不对，手动算小例子是定位问题最快的方式，比对着调试器看半天递归栈管用得多。这些数据基本覆盖了所有边界：空、单、顺序、逆序、重复、负数。
5. 另一种经典思路：树状数组求逆序对
5.1 树状数组的定位和复杂度
树状数组（Binary Indexed Tree，BIT）是一种支持单点修改和前缀和查询的数据结构，两个操作都是 O(log n)。用它求逆序对的思路和归并完全不同：归并是“在排序过程中顺便数”，树状数组则是“逐个插入元素，随时查询已经入场的元素里有多少个比当前元素大”。
整体流程是：先把原数组离散化，也就是把每个数映射成它在所有数里的排名，这样数值范围就变成了 1 到去重后的个数 m；然后从左到右遍历数组，对当前元素 x，查询树状数组的 sum(pos)，得到已经遍历过的数里小于等于 x 的个数，再用已遍历总数 i 减去这个值，得到大于 x 的个数，累加进答案；最后在当前位置的排名 pos 上加 1，表示这个数已经入场。整个过程每个元素做一次查询、一次修改，总复杂度 O(n log n)。
5.2 离散化：把原数映射成排名
为什么要离散化？因为树状数组的下标必须是正整数，而原数组可能是负数、浮点数、很大很离散的正整数，直接按下标开数组是不现实的。离散化的标准做法是把原数组复制一份，排序去重，然后用 lower_bound 找到每个原元素在去重排序数组中的位置，加 1 作为排名。
举个小例子：设数组 [3, 1, 2, 5, 4]，排序去重后得到 [1,2,3,4,5]。那么 3 的排名是 3，1 的排名是 1，2 的排名是 2，5 的排名是 5，4 的排名是 4。这样原数组的每个值都被压到连续的 1 到 5 上，树状数组只需要开 6 个 int 的空间。如果原数组很大且重复多，去重后 m 可能远小于 n，内存会更省。这一步本质上就是把一个“值域”问题转换成一个“排名”问题，也是树状数组类题目的标配操作。
5.3 紧凑的模板代码
下面这套 C++ 代码可以用在很多逆序对类问题上，核心就是树状数组的 add 和 sum 两个函数。add 负责单点修改，sum 负责前缀和查询，它们都依赖idx & -idx来定位父节点或前一个区间。
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> bit; int m; void add(int idx, int x) { while (idx <= m) { bit[idx] += x; idx += idx & -idx; } } int sum(int idx) { int res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & -idx; } return res; } int main() { vector<int> arr = {3, 1, 2, 5, 4}; vector<int> sorted = arr; sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); m = sorted.size(); bit.assign(m + 1, 0); ll ans = 0; for (int i = 0; i < (int)arr.size(); i++) { int pos = lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin() + 1; ans += i - sum(pos); // 已遍历的数中大于当前元素的个数 add(pos, 1); } cout << ans << endl; return 0; }这里要注意：sum(pos) 查询的是“小于等于 pos 的已入场个数”，所以答案累加用的是i - sum(pos)。其中 i 是当前元素之前已经遍历的元素个数。每次循环后 add(pos, 1)，把当前元素放入树状数组。整个思路的关键是：每个新元素只和它之前的元素比较，所以不会重复计数。如果改成从右往左遍历，也可以写ans += sum(pos - 1)，统计的是右侧小于当前元素的个数，两种写法等价，挑一种记住就好。
5.4 归并 vs 树状数组，怎么选
| 对比维度 | 归并排序法 | 树状数组法 |
|---|---|---|
| 核心思想 | 分治合并时利用有序性计数 | 频次统计 + 前缀和查询 |
| 时间复杂度 | O(n log n) | O(n log n) |
| 额外空间 | O(n) | O(n) |
| 实现难度 | 理解合并公式即可 | 需要掌握树状数组模板和离散化 |
| 是否改变原数组 | 会改变，合并时直接写回 | 不改变原数组，只复制排序去重数组 |
| 扩展场景 | 适合一次性完整数组统计 | 适合动态插入元素、在线统计 |
我的选择经验很简单：如果只是求一个完整数组的逆序对，优先用归并写法，代码短，逻辑也直观；如果问题是动态的，比如数据流式不断加入、每次加入后都要查逆序对数量，那就用树状数组，因为它天然支持在线更新。还有一些题目会要求你同时求出每个元素对应的逆序对个数，这时候树状数组从左到右遍历的写法更好改，归并法则需要额外记录。
6. 常见问题与排查技巧实录
6.1 六个高频问题速查表
我把实际里遇到比较多的现象、可能原因和解决思路整理成了下表，按出现频率排序。这里的现象大多是从真实排错现场来的，很有参考价值。
| 现象 | 大概原因 | 解决办法 |
|---|---|---|
| 答案比预期大不少 | 相等元素被当逆序对计算 | 合并判断改成 <= |
| 结果出现负数或异常大 | 用 int 保存答案，累加溢出 | 换成 long long / long |
| 数组越界或段错误 | 临时数组大小算错，或越界赋值 | 检查 tmp 大小和 k、l、r 取值 |
| 递归后原数组变成有序 | 归并排序本来就有排序效果 | 重新备份原数组，或在调用前保存副本 |
| 多个样例累计答案错误 | 全局变量 ans 没在每组用例前清零 | 每组输入前执行 ans = 0 |
| 数据稍大就超时 | 暴力 O(n^2) 或频繁分配小数组 | 改用归并/树状数组，并考虑复用临时数组 |
这些问题里，前两个最容易在平时练习时遇到。第三个要特别警惕，因为递归函数里如果 tmp 的大小写成 r - l 而不是 r - l + 1，最后一位就会写越界，调试时未必马上崩，但结果可能莫名其妙错。为避免这种问题，统一使用 vector 代替裸数组，越界时至少能更快暴露出来。第四个需要特别说明，如果你不小心修改了原数组，会影响后续依赖原数组的操作，所以调用前最好先备份。
6.2 一次实际排查过程：计数结果比答案少了很多
我帮人看一段逆序对代码时，现象是小数据测试全对，一到 10^5 规模数据，答案比暴力对拍结果少了一大截。第一反应是数据范围导致的精度问题，但换成 long long 之后依然少。后来用二分法缩小范围，发现是递归函数里返回值和全局变量混用了：他的 merge 函数内部有一个局部 long long ans，每次合并时做的累加都加在局部变量上，但函数没有把合并阶段的计数通过返回值传出去，只返回了递归子区间的结果。这样每层跨区间的逆序对全被丢掉了，数据越大丢得越多。
具体表现就是：完全逆序的 [5,4,3,2,1]，在递归最深层的合并中计数会累加，但到上层时没有继续传递，最终结果只包含底层的一部分，自然比真实值小。排查方法也很简单：用一个完全逆序的小数组，在每次触发ans += mid - i + 1的地方打印日志，几行就能看清哪一层计数没有向上汇总。这个问题提醒我，写递归统计时，要么统一用全局变量，要么统一用返回值，千万不要两个混着用。
6.3 三个能让你少走弯路的小技巧
第一个技巧是在本地准备暴力对拍函数。把 O(n^2) 的暴力函数和归并函数同时跑，用随机小数组验证结果是否一致，一旦发现不一致，立刻能定位到实现细节。第二个技巧是每次提交前先过一遍边界样例，空数组、单元素、升序、降序、重复元素，这五组能覆盖绝大多数递归边界问题。第三个技巧是把临时数组合并到全局复用，既减少分配开销，又避免每次递归重新申请带来的不确定性能波动。这三个技巧单独看都很小，但组合起来能省很多调试时间。
逆序对这道题的代码量不大，真正的难点在于细节，把这些细节变成肌肉记忆之后，你看归并、树状数组相关的其他题目会顺畅很多。遇到“数组中的逆序对”相关的变体题，我也是靠这套思路快速入手的：先确认是静态完整数组还是动态在线查询，再决定用归并还是树状数组，最后用五组固定样例加对拍收尾。
