分治法求逆序对的核心思路是：将数组递归二分，先统计左右子区间内部逆序对，再在合并两个有序子数组时，当左段元素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 <h3>递归实现时容易漏掉哪些边界和细节</h3>
<p>常见错误不是逻辑错，而是下标越界、统计时机错、数据类型错：</p>
<ul>
<li>
<code>mid</code> 计算写成 <code>(left + right) / 2</code> 没问题，但推荐 <code>left + (right - left) / 2</code> 防止 <code>int</code> 溢出（虽本题 <code>n ≤ 5e4</code> 不会溢出，但习惯要养）</li>
<li>递归调用顺序必须是：先左右子区间各自统计，再归并时统计跨区逆序对；漏掉任一子调用，结果就少一半</li>
<li>归并函数里 <code>inv_count += mid - i + 1</code> 的 <code>+1</code> 容易遗漏，导致少算一个（比如 <code>i == mid</code> 时，只剩 1 个元素，应加 1）</li>
<li>主函数入口要传原始数组副本，或确保输入可修改；若需保持原数组不变，得先 <code>vector<int> aux = nums</int></code>
</li>
</ul>
<h3>为什么不能用快排或堆排改写来求逆序对</h3>
<p>快排划分过程无法保证「左侧下标一定小于右侧下标」，交换操作会打乱原始位置关系，无法可靠累计跨段逆序；堆排更无天然的分段有序结构。只有归并排序在合并前保证左右子数组各自有序，且合并过程天然按原下标顺序扫描，才能无损捕获所有 <code>i<j> 且 <code>nums[i]>nums[j]</code> 的组合。</j></code></p>
<p>另外，STL 的 <code>std::inplace_merge</code> 虽能简化归并，但它不暴露比较过程，无法插入统计逻辑，所以必须手写归并逻辑。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
