问题定义
逆序对（Inversion）指满足 i < j 且 a[i] > a[j] 的数对 (a[i], a[j])。暴力两两比较是 O(n²)，而”离散化 + 树状数组“可以在 O(n log n) 内完成统计，思路与归并排序并列的两大经典解法之一。
算法思路
把”统计逆序对”转化为”动态统计比当前元素小的个数”：
- 离散化：若数值范围大（如 10⁹）或含负数，先排序去重，把每个值映射为 1..n 的排名，保持大小关系不变；
- 从右向左遍历：每遇到
a[i]，先查询树状数组中小于 a[i] 的元素个数（这些元素都在 i 的右侧），累加到答案； - 插入：
update(a[i], 1)，把当前元素放入树状数组，供左侧元素统计。
关键点：从右向左保证查询时树状数组里只包含右侧已扫描的元素；query(a[i]-1) 统计的是严格小于 a[i] 的个数（用 query(a[i]) 会把相等元素也算进去，重复元素时出错）。
C++ 实现
#include <vector>
#include <algorithm>
using namespace std;
class FenwickTree {
private:
vector<int> tree;
int lowbit(int x) { return x & -x; }
public:
FenwickTree(int n) : tree(n + 1, 0) {}
void update(int x, int delta) {
while (x < (int)tree.size()) {
tree[x] += delta;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
};
long long countInversions(vector<int>& nums) {
// 1. 离散化
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (int& num : nums)
num = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;
// 2. 从右向左统计
FenwickTree ft(nums.size());
long long res = 0; // 用 long long！n 可达 1e5，答案可能爆 int
for (int i = nums.size() - 1; i >= 0; --i) {
res += ft.query(nums[i] - 1); // 右侧比 nums[i] 小的个数
ft.update(nums[i], 1); // 插入当前元素
}
return res;
}
示例：[3, 1, 4, 2]
离散化后 [2, 1, 3, 4]，从右向左：
- i=3（值 4）：query(3) = 0，累计 0，插入 4；
- i=2（值 2）：query(1) = 1（只有 1 比 2 小），累计 1，插入 2；
- i=1（值 1）：query(0) = 0，插入 1；
- i=0（值 3）：query(2) = 1（1 比 3 小），累计 2。
总逆序对 = 2，对应 (3,1) 和 (4,2)，正确。
复杂度
- 离散化：O(n log n)（排序 + 去重）；
- 树状数组操作：每次 update/query O(log n)，共 O(n log n)；
- 总复杂度 O(n log n)，空间 O(n)。
扩展
- 求每个元素的逆序数：遍历时把每次
query(a[i]-1)的结果存入数组即可； - 重复元素：离散化保留重复值，用
query(a[i]-1)仍然只统计严格小于的个数，正确性不受影响； - 与归并排序对比：归并排序离线 O(n log n)、无需离散化；BIT 方案支持在线动态插入（如排行榜实时统计）。看场景选。
实战体会
两种遍历方向本质等价。从右向左是”统计右边比自己小的”，从左向右则是”统计左边比自己大的”——query(a[i]-1) 和 i - query(a[i]) 是同一类查询的对称写法。刷题时固定一种即可，省得每次现推。
离散化顺带解决了负数。BIT 下标要求非负，离散化映射到 1..n 后负数也自然可用。实际工作里给排行榜算”前面有多少人分数比我高”用的就是这个套路，支持在线插入，这是归并排序做不到的。
重复元素是翻车高发点。求”严格小于”必须用 query(a[i]-1) 而非 query(a[i])，否则相等元素被多算。面试里这个细节常用来区分”背过模板”和”真正理解”。
别忘了 long long。n=10⁵ 时逆序对数最多约 5×10⁹，int 会溢出——这是我第一次提交 WA 的原因。
