请使用树状数组求逆序对

树状数组（Fenwick tree）是一种用于高效求解数列前缀和（Prefix Sum）问题的数据结构，而求逆序对也是一种经典的问题。

假设有个长度为 n 的数组 a，我们要求其中逆序对的数量，即所有 i < j 且 a[i] > a[j] 的 (i,j) 对数。这个问题可以用归并排序的思想求解，但是这里我们介绍一种使用树状数组的解法。

思路如下：

1. 将原数组 a 复制一份并排序，得到新数组 b，将 b 中的每个元素在原数组 a 中的下标记录在数组 c 中。
2. 从右往左遍历 a，对于每个元素 a[i]，在树状数组中查询前缀和 sum(c[i]-1)，即小于 a[i] 的元素个数，将结果累加到逆序对计数器 ans 中。
3. 将 a[i] 在数组 c 中对应的位置在树状数组中更新为 1。

下面是使用 Python 实现的代码：

def lowbit(x):
    return x & -x

def update(bit, x, val):
    n = len(bit)
    while x <= n:
        bit[x] += val
        x += lowbit(x)

def query(bit, x):
    res = 0
    while x > 0:
        res += bit[x]
        x -= lowbit(x)
    return res

def count_inversions(a):
    n = len(a)
    b = sorted(a)
    c = {v: i+1 for i, v in enumerate(b)}
    bit = [0] * (n+1)
    ans = 0
    for i in range(n-1, -1, -1):
        ans += query(bit, c[a[i]]-1)
        update(bit, c[a[i]], 1)
    return ans

其中，lowbit 函数是计算 x 的最低位 1 所代表的值；update 函数是树状数组的更新操作；query 函数是树状数组的查询操作；count_inversions 函数是主函数，用于计算逆序对数量。

时间复杂度为 O(nlogn)。