分治法求逆序对的核心思路是：将数组递归二分，先统计左右子区间内部逆序对，再在合并两个有序子数组时，当左段元素nums[i] > nums[j]（右段），立即累加mid−i+1个跨区间逆序对，利用有序性实现O(n)批量统计，最终时间复杂度为O(n log n)。
分治法求逆序对的核心思路是什么
逆序对的本质是：对于数组 nums[i] > nums[j] 且 i 。暴力双重循环是 <code>O(n²)，而分治（归并排序改造）能降到 O(n log n)——关键在于：**在归并两个已排序子数组时，左半部分的某个元素 nums[i] 如果大于右半部分的 nums[j]，那么它必然大于从 j 开始的所有右半元素**。
所以不是“数每一对”，而是“数贡献”：当 nums[i] > nums[j] 成立时，直接累加 mid - i + 1（即左半中从 i 到末尾的元素个数），因为它们都比 nums[j] 大，且下标更小。
归并过程中怎么安全统计逆序对数量
必须在归并的 比较阶段 统计，不能在复制或合并后补算；且只在「左元素大于右元素」时触发累加，其他情况不处理。
- 用一个全局或引用传入的
long long &inv_count累加，避免整型溢出（n=5e4时逆序对最多约1.25e9，但极端情况可能超int） - 递归边界为
left >= right，单元素无逆序对 - 归并时，若
nums[i] ，正常取左；若 <code>nums[i] > nums[j]，取右，并执行inv_count += mid - i + 1 - 注意：必须用临时数组做归并，不能原地覆盖，否则破坏原始顺序影响上层统计
void merge(vector<int>& nums, int left, int mid, int right, long long& inv_count) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
inv_count += mid - i + 1; // 关键：左半剩余元素全构成逆序对
}
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (i = left, k = 0; i <= right; ++i, ++k) nums[i] = temp[k];
}
递归实现时容易漏掉哪些边界和细节
常见错误不是逻辑错，而是下标越界、统计时机错、数据类型错：
立即学习“C++免费学习笔记（深入）”；
-
mid计算写成(left + right) / 2没问题，但推荐left + (right - left) / 2防止int溢出（虽本题n ≤ 5e4不会溢出，但习惯要养） - 递归调用顺序必须是：先左右子区间各自统计，再归并时统计跨区逆序对；漏掉任一子调用，结果就少一半
- 归并函数里
inv_count += mid - i + 1的+1容易遗漏，导致少算一个（比如i == mid时，只剩 1 个元素，应加 1） - 主函数入口要传原始数组副本，或确保输入可修改；若需保持原数组不变，得先
vector<int> aux = nums</int>
为什么不能用快排或堆排改写来求逆序对
快排划分过程无法保证「左侧下标一定小于右侧下标」，交换操作会打乱原始位置关系，无法可靠累计跨段逆序；堆排更无天然的分段有序结构。只有归并排序在合并前保证左右子数组各自有序，且合并过程天然按原下标顺序扫描，才能无损捕获所有 i<j> 且 <code>nums[i]>nums[j] 的组合。
另外，STL 的 std::inplace_merge 虽能简化归并，但它不暴露比较过程，无法插入统计逻辑，所以必须手写归并逻辑。
