如果你第一次接触逆序对这个概念可能会觉得这不过又是一个“两层循环就能数完”的数组小问题。真正写过的人才知道当数组规模来到几十万甚至上百万时暴力解法根本活不过评测样例。而“逆序对”这三个字一旦和“归并”绑定在一起就成了一道非常经典的分治应用题一边排序一边把答案数出来复杂度稳定在 O(n log n)。这篇文章我打算把这个过程彻底拆开讲从定义、暴力解到归并原理、三种语言实现再到边界细节、树状数组方案和排查经验把这道题变成你能随时复用的一套“肌肉记忆”。1. 什么是逆序对定义、暴力解与真正的需求1.1 逆序对的定义用一个例子讲明白假设现在有一个数组 [3, 1, 2]。按逆序对的定义所有满足“前面的数比后面的数大”的位置组合都算3 和 1 是一对因为 3 在 1 前面且 3 13 和 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 vectorint 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-i1”。竞赛中它则是分治和数据结构两个方向的基础题掌握归并写法之后再看树状数组解法就会顺很多。这篇文章后面所有内容都是为了把这条能力链串起来让你既能写出能跑的代码又能真正理解背后的计数逻辑。2. 用归并排序数逆序对原理拆解2.1 先复习归并排序的核心流程归并排序的处理对象是一个数组流程可以概括成三步分、治、合。第一步“分”把当前区间 [l, r] 从中间位置一分为二变成 [l, mid] 和 [mid1, r]第二步“治”递归地对左右两个子区间分别做归并排序让它们各自变成有序序列第三步“合”把两个已经有序的子区间交错合并成一个更大的有序区间。合并的操作很像整理两堆扑克牌两堆牌各自按从小到大排好了现在要合成一堆。每次只看两堆最顶上那张谁小谁就先放到结果堆里。这个过程的复杂度是 O(n)因为每张牌只被比较和移动一次。整个归并排序的复杂度 T(n)2T(n/2)O(n)解出来就是 O(n log n)。看起来这个排序过程和逆序对没什么直接关系但关键就在合并这一步合并两个有序子区间时我们天然知道左边区间里的元素在原数组中全部位于右边区间元素之前。也就是说如果发现左边当前的某个元素比右边当前元素大那么左边当前元素后面的所有元素也都比右边当前元素大而且都位于它前面。这些组合全部都是逆序对。这个洞察是整个算法的灵魂。2.2 逆序对被“数”出来的关键瞬间假设当前正在合并左区间 [l, mid] 和右区间 [mid1, 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]右区间是 [mid1, 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(vectorint 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); vectorint 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; vectorint 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。你可以在本地把这段代码跑起来然后换着输入验证。我一般会再跑这些边界样例空数组n0、单元素、完全升序、完全降序、全部相同元素。这些样例都不需要很多数据却能快速暴露递归边界和相等判断的问题。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 位有符号在 n10^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 作为写回起点运行过程始终复用这一块内存。vectorint tmpArr; void merge(vectorint 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 TreeBIT是一种支持单点修改和前缀和查询的数据结构两个操作都是 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 的排名是 31 的排名是 12 的排名是 25 的排名是 54 的排名是 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; vectorint 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() { vectorint arr {3, 1, 2, 5, 4}; vectorint 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) 的暴力函数和归并函数同时跑用随机小数组验证结果是否一致一旦发现不一致立刻能定位到实现细节。第二个技巧是每次提交前先过一遍边界样例空数组、单元素、升序、降序、重复元素这五组能覆盖绝大多数递归边界问题。第三个技巧是把临时数组合并到全局复用既减少分配开销又避免每次递归重新申请带来的不确定性能波动。这三个技巧单独看都很小但组合起来能省很多调试时间。逆序对这道题的代码量不大真正的难点在于细节把这些细节变成肌肉记忆之后你看归并、树状数组相关的其他题目会顺畅很多。遇到“数组中的逆序对”相关的变体题我也是靠这套思路快速入手的先确认是静态完整数组还是动态在线查询再决定用归并还是树状数组最后用五组固定样例加对拍收尾。
逆序对怎么求？归并排序与树状数组两种高效解法详解
如果你第一次接触逆序对这个概念可能会觉得这不过又是一个“两层循环就能数完”的数组小问题。真正写过的人才知道当数组规模来到几十万甚至上百万时暴力解法根本活不过评测样例。而“逆序对”这三个字一旦和“归并”绑定在一起就成了一道非常经典的分治应用题一边排序一边把答案数出来复杂度稳定在 O(n log n)。这篇文章我打算把这个过程彻底拆开讲从定义、暴力解到归并原理、三种语言实现再到边界细节、树状数组方案和排查经验把这道题变成你能随时复用的一套“肌肉记忆”。1. 什么是逆序对定义、暴力解与真正的需求1.1 逆序对的定义用一个例子讲明白假设现在有一个数组 [3, 1, 2]。按逆序对的定义所有满足“前面的数比后面的数大”的位置组合都算3 和 1 是一对因为 3 在 1 前面且 3 13 和 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 vectorint 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-i1”。竞赛中它则是分治和数据结构两个方向的基础题掌握归并写法之后再看树状数组解法就会顺很多。这篇文章后面所有内容都是为了把这条能力链串起来让你既能写出能跑的代码又能真正理解背后的计数逻辑。2. 用归并排序数逆序对原理拆解2.1 先复习归并排序的核心流程归并排序的处理对象是一个数组流程可以概括成三步分、治、合。第一步“分”把当前区间 [l, r] 从中间位置一分为二变成 [l, mid] 和 [mid1, r]第二步“治”递归地对左右两个子区间分别做归并排序让它们各自变成有序序列第三步“合”把两个已经有序的子区间交错合并成一个更大的有序区间。合并的操作很像整理两堆扑克牌两堆牌各自按从小到大排好了现在要合成一堆。每次只看两堆最顶上那张谁小谁就先放到结果堆里。这个过程的复杂度是 O(n)因为每张牌只被比较和移动一次。整个归并排序的复杂度 T(n)2T(n/2)O(n)解出来就是 O(n log n)。看起来这个排序过程和逆序对没什么直接关系但关键就在合并这一步合并两个有序子区间时我们天然知道左边区间里的元素在原数组中全部位于右边区间元素之前。也就是说如果发现左边当前的某个元素比右边当前元素大那么左边当前元素后面的所有元素也都比右边当前元素大而且都位于它前面。这些组合全部都是逆序对。这个洞察是整个算法的灵魂。2.2 逆序对被“数”出来的关键瞬间假设当前正在合并左区间 [l, mid] 和右区间 [mid1, 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]右区间是 [mid1, 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(vectorint 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); vectorint 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; vectorint 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。你可以在本地把这段代码跑起来然后换着输入验证。我一般会再跑这些边界样例空数组n0、单元素、完全升序、完全降序、全部相同元素。这些样例都不需要很多数据却能快速暴露递归边界和相等判断的问题。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 位有符号在 n10^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 作为写回起点运行过程始终复用这一块内存。vectorint tmpArr; void merge(vectorint 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 TreeBIT是一种支持单点修改和前缀和查询的数据结构两个操作都是 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 的排名是 31 的排名是 12 的排名是 25 的排名是 54 的排名是 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; vectorint 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() { vectorint arr {3, 1, 2, 5, 4}; vectorint 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) 的暴力函数和归并函数同时跑用随机小数组验证结果是否一致一旦发现不一致立刻能定位到实现细节。第二个技巧是每次提交前先过一遍边界样例空数组、单元素、升序、降序、重复元素这五组能覆盖绝大多数递归边界问题。第三个技巧是把临时数组合并到全局复用既减少分配开销又避免每次递归重新申请带来的不确定性能波动。这三个技巧单独看都很小但组合起来能省很多调试时间。逆序对这道题的代码量不大真正的难点在于细节把这些细节变成肌肉记忆之后你看归并、树状数组相关的其他题目会顺畅很多。遇到“数组中的逆序对”相关的变体题我也是靠这套思路快速入手的先确认是静态完整数组还是动态在线查询再决定用归并还是树状数组最后用五组固定样例加对拍收尾。
