预计阅读时间：8 分钟
一文解决逆序数
数组里满足 i < j 且 a[i] > a[j] 的一对下标叫一个逆序对，逆序数就是这种对的总数。一道逆序数，四种写法，从面试到竞赛一网打尽。计算逆序数有两种思路：
- 归并排序：合并左右两个已排好序的半段时，每当右半段的元素先出列，答案就加上左半段还没出列的元素个数（面试版代码里的
n - p1）。两边相等时让左边先出列，所以比较用严格的>：写成>=会把相等的数也算成逆序，[2,2,2,2]会得到 6 而不是 0； - 值域计数：先把值离散化成名次 rank（值在去重排序后的位置，取 1 到 m，m 是不同值的个数），从左往右逐个把元素 rank 位置的计数加一；当前元素的逆序贡献（即它左边比它大的元素个数）等于加一之前值域区间 $[\text{rank}+1, m]$ 上的计数和——需要单点修改 + 区间求和的数据结构。
复杂度：归并排序时间 $O(n \log n)$、额外空间 $O(n)$，下面切片版和索引版的复杂度相同，只是常数不同；值域计数先排序离散化，再做 n 次单点修改和区间查询，时间也是 $O(n \log n)$，空间上树状数组开长度 m + 1 的数组，即 $O(m)$，线段树开长度 4m 的数组。
leetcode 上有一道数据规模较小的模板题（长度不超过 $5 \times 10^4$，洛谷 P1908 的 n 到 $5 \times 10^5$），下面四份代码都以它为载体。
思路一：归并排序
面试版（切片归并）
一般来说面试写出这版就够了：
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
if a == []:
return 0
ans = 0
def change(nums1, nums2):
nonlocal ans
p1 = 0
p2 = 0
n = len(nums1)
m = len(nums2)
res = []
while p1 < n and p2 < m:
if nums1[p1] > nums2[p2]:
res.append(nums2[p2])
p2 += 1
ans += (n - p1)
else:
res.append(nums1[p1])
p1 += 1
res.extend(nums1[p1: ])
res.extend(nums2[p2: ])
return res
def merge(nums):
n = len(nums)
if n == 1:
return nums
left = 0
right = n - 1
mid = (left + right) // 2
l = merge(nums[: mid + 1])
r = merge(nums[mid + 1: ])
return change(l, r)
merge(a)
return ans
这版的函数名起反了：merge 实际是递归拆分、排序，change 才是合并两个有序段。
索引版（下标归并）
这版不切片，按下标区间 [l, r] 递归，辅助数组 res 只开一次，合并时先写进 res，再回写到原数组的这一段。它的用处是结构干净：不反复切片建新列表，辅助数组只开一次，几乎可以逐行翻成 C++ / Java。它在 CPython 里并不比切片版快：$5 \times 10^5$ 个随机数实测，Python 3.12 上切片版 0.50 秒、这版 0.71 秒，Python 3.9 上 0.90 秒对 1.17 秒。
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
if a == []:
return 0
ans = 0
res = [0] * len(a)
def change(l, mid, r):
nonlocal ans
p1 = l
p2 = mid + 1
n = mid - l + 1
k = l
while p1 <= mid and p2 <= r:
if a[p1] > a[p2]:
res[k] = a[p2]
p2 += 1
ans += (n - p1 + l)
else:
res[k] = a[p1]
p1 += 1
k += 1
while p1 != mid + 1:
res[k] = a[p1]
k += 1
p1 += 1
while p2 != r + 1:
res[k] = a[p2]
k += 1
p2 += 1
for i in range(l, r + 1):
a[i] = res[i]
def merge(left, right):
if left >= right:
return
mid = (left + right) // 2
merge(left, mid)
merge(mid + 1, right)
change(left, mid, right)
merge(0, len(a) - 1)
return ans
思路二：值域计数
第二种思路需要「单点修改 + 区间求和」，线段树、树状数组都能胜任，两种都写一遍。值先离散化成 rank。
线段树
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 * n
def update(self, root):
self.tree[root] = self.tree[root * 2] + self.tree[root * 2 + 1]
def build(self, left, right, root):
if left > right:
return
if left == right:
self.tree[root] = self.nums[left - 1]
return
mid = (left + right) // 2
self.build(left, mid, root * 2)
self.build(mid + 1, right, root * 2 + 1)
self.update(root)
def change(self, A, v, left, right, root):
if left > right:
return
if left == right:
self.tree[root] = v
return
mid = (left + right) // 2
if left <= A <= mid:
self.change(A, v, left, mid, root * 2)
if mid + 1 <= A <= right:
self.change(A, v, mid + 1, right, root * 2 + 1)
self.update(root)
def query(self, A, B, left, right, root):
if A <= left <= right <= B:
return self.tree[root]
mid = (left + right) // 2
res = 0
if A <= mid:
res += self.query(A, B, left, mid, root * 2)
if B >= mid + 1:
res += self.query(A, B, mid + 1, right, root * 2 + 1)
return res
def get_ranks(nums):
new_nums = sorted(list(set(nums)))
hp = {v: r + 1 for r, v in enumerate(new_nums)}
return hp
hp = get_ranks(a)
new_a = [0] * len(hp)
tree = segment_tree(new_a)
tree.build(1, len(hp), 1)
ans = 0
for i in a:
p = hp[i]
if p + 1 <= len(hp):
ans += tree.query(p + 1, len(hp), 1, len(hp), 1)
temp = tree.query(p, p, 1, len(hp), 1)
tree.change(p, temp + 1, 1, len(hp), 1)
return ans
树状数组
同样的思路，树状数组写起来短得多：
class Solution:
def reversePairs(self, record: List[int]) -> int:
a = record
class binary_indexed_tree:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums
self.tree = [0] * (self.n + 1)
def lowbit(self, x):
return x & -x
def change(self, pos, v):
while pos <= self.n:
self.tree[pos] += v
pos += self.lowbit(pos)
def query(self, pos):
res = 0
while pos > 0:
res += self.tree[pos]
pos -= self.lowbit(pos)
return res
def get_ranks(nums):
new_nums = sorted(list(set(nums)))
hp = {v: r + 1 for r, v in enumerate(new_nums)}
return hp
hp = get_ranks(a)
new_a = [0] * len(hp)
tree = binary_indexed_tree(new_a)
ans = 0
for i in a:
p = hp[i]
ans += tree.query(len(hp)) - tree.query(p)
tree.change(p, 1)
return ans
区间和用两次前缀查询相减：query(len(hp)) - query(p)。其中 query(len(hp)) 恒等于已经插入的元素个数，也可以直接用循环下标代替，省掉一次查询。
本文由 aboom 原创，转载请注明出处。