统计满足i<j且array[i]>array[j]的数组逆序对的高效实现咨询

原双重循环实现超时的根因 #

当前写法的时间复杂度为O(N²)，当N达到1e5量级时，累计循环运算量可达1e10次，远超出Python等脚本语言的常规时间阈值，必然触发时间限制。

可适配N=1e5规模的实现思路 #

我们要统计的满足i < j且array[i] > array[j]的元素对，就是经典的数组逆序对。这类问题可以通过*O(N log N)*时间复杂度的算法解决，完全覆盖1e5的规模约束，主流实现方案包括：

• 归并排序分治计数：在归并排序的区间合并环节，顺带统计跨区间的逆序对数量，不需要额外的全量遍历
• 树状数组（Fenwick树）计数：先对数组元素做离散化压缩取值范围，从后往前遍历数组，动态查询已遍历元素中小于当前值的元素数量，累加得到总逆序对数

参考实现代码（树状数组版本） #

# 树状数组基础实现
class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)
    
    def update(self, pos, delta):
        while pos < len(self.tree):
            self.tree[pos] += delta
            pos += pos & -pos
    
    def query(self, pos):
        count = 0
        while pos > 0:
            count += self.tree[pos]
            pos -= pos & -pos
        return count

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    # 对数组元素做离散化，压缩取值范围
    sorted_vals = sorted(set(arr))
    val_rank = {val: idx+1 for idx, val in enumerate(sorted_vals)}
    ft = FenwickTree(len(sorted_vals))
    total = 0
    # 从后往前遍历统计逆序对
    for num in reversed(arr):
        rank = val_rank[num]
        # 累加已经出现的、比当前值小的元素数量
        total += ft.query(rank - 1)
        ft.update(rank, 1)
    print(total)

给定测试用例的验证结果 #

针对输入：

10
7 6 2 4 1 5 10 3 9 8

代码运行后输出结果为19，与手工统计的逆序对总数完全一致。

补充说明：离散化步骤的作用是压缩元素的取值范围，避免数组元素值过大导致树状数组申请不必要的内存，同时对重复元素的统计逻辑完全兼容。

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