如何用O(n log n)算法计算数组中的大逆序数？

方法一：扩展归并排序 #

完全可以基于常规逆序数的归并排序解法扩展，核心思路是在分治合并阶段，针对性统计满足a[i] > a[j] + k（i在左半区间，j在右半区间）的跨区间大逆序对，再加上左右子数组内部的大逆序对总数。

具体步骤：

• 分治拆分：将数组递归拆分为左右两个子数组，分别计算子数组内部的大逆序对数量。
• 合并统计跨区间大逆序对：
  合并前，左右子数组已经是有序的（归并排序的特性）。对于右子数组中的每个元素a[j]，利用左子数组的有序性，通过二分查找快速定位第一个大于a[j] + k的元素位置。左子数组中从该位置到末尾的所有元素，都满足a[i] > a[j] + k，这部分的数量为左子数组长度减去该位置的索引，将其累加到总计数中。
• 合并有序数组：完成统计后，按常规归并排序的方式合并左右子数组，供上层递归使用。

时间复杂度：每次二分查找为O(log n)，每个元素仅被处理一次，递归分治的时间为O(n log n)，整体复杂度保持O(n log n)。

方法二：树状数组（Fenwick Tree） #

这种方法灵活高效，适合处理各类带条件的逆序统计问题，步骤如下：

1. 离散化处理：由于数组元素可能范围极大，先将所有元素（包括a[i] - k）映射到连续的整数区间，压缩树状数组的空间开销。
2. 从后往前遍历数组：
   • 对于当前元素a[i]，查询树状数组中小于a[i] - k的元素数量——这就是以i为左端点的大逆序对数量（对应j > i且a[i] > a[j] + k），将其累加到总计数中。
   • 将当前元素a[i]插入树状数组，供后续元素查询使用。
3. 树状数组操作：需实现两个核心操作：
   • 前缀和查询：统计小于等于某个值的元素总数。
   • 单点更新：插入元素时更新对应位置的计数。

若选择从前往后遍历，逻辑类似：对于每个元素a[j]，查询已插入元素中大于a[j] + k的数量（即已插入元素总数减去小于等于a[j] + k的元素数量），累加后再插入a[j]即可。

时间复杂度：离散化耗时O(n log n)，每个元素的查询与更新操作均为O(log n)，整体复杂度为O(n log n)。

特殊情况调整 #

如果你的实际需求是统计位置间隔超过k的逆序对（即i < j且j - i > k且a[i] > a[j]），只需对上述方法稍作修改：

• 归并排序方法：合并时仅统计右子数组中与左子数组元素位置差超过k的部分，或在分治阶段限制跨区间的j范围。
• 树状数组方法：遍历到i时，仅查询i+k+1之后的元素（可通过离线预处理位置信息实现）。

内容的提问来源于stack exchange，提问作者Piglet