我知道这个问题之前已经讨论过，但我有兴趣使用二进制索引树来做这个。我找到了这个链接来展示如何做。我没有完全按照解释。有人可以给我解释一下为什么下面给出的内容是真的。
Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do:
1) Add j-sum(A[j]) to the number of inversions
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively
counts the number of time value A[j] is seen so far)
我不明白为什么这有效。
当一个元素大于数组中跟随它的某个元素时，就会发生反转。
我们可以通过按第二个元素对反转进行分组来计算反转。例如，在数组 [4, 3, 1, 2] 中，元素对 (4, 3), (4, 1), (4, 2), (3, 1) 和 (3, 2) 是倒置。我们按第二个元素对它们进行分组，因此：[[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]]。
我们依次考虑每个元素，并计算它是第二个元素的反转次数。在示例中，元素 4 是 0 反转中的第二个元素，元素 3 是 1 反转中的第二个元素，元素 1 和 2 中的每个反转 2。
为了使任何给定元素成为反转的第二个元素，数组中必须有一个更大的元素在它之前的某个位置。
我们通过从左到右遍历数组来有效地执行计数，并始终使用 BIT 跟踪到目前为止每个值的元素数量。最初我们的频率表将是 [0, 0, 0, 0]，因为我们根本没有看到任何元素。在我们访问 4 之后，我们更新它的频率，给出 [0, 0, 0, 1]。访问3之后，[0,0,1,1]，以此类推。
每次我们访问一个位置时，我们使用 BIT 来找出到目前为止访问过的元素有多少大于它。因此，例如当我们遇到 1 时，BIT 当前包含 [0, 0, 1, 1]，表示到目前为止有 0 个 1 和 2、一个 3 和一个 4。通过添加值 0 + 1 + 1 ，我们计算到目前为止大于 1 的元素的数量。
将所有这些单独的计数相加得到反转的总数。
请注意，通常，您必须使用坐标压缩才能使其有效。例如，如果您的初始数组包含像 A = [92, 631, 50, 7] 这样的数字，则不应分配具有数百个元素的 BIT。相反，对数组进行排序以确定 7 < 50 < 92 < 631，这允许我们分配等级 7 => 1, 50 => 2, 92 => 3, 631 => 4; 然后用它的等级替换每个元素，得到 B = [3, 4, 2, 1]。该数组的反转次数将与原始数组相同，因为 B[i] > B[j] 当且仅当 A[i] > A[j]。
（注意：真正的程序员可能会使用从零开始的索引。）