我知道之前已经讨论过这个问题，但我有兴趣使用二叉索引树来做这个。我找到了 this 链接以显示如何操作。我不太理解解释。有人可以给我解释为什么以下给出的是真的。
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]，表示到目前为止有零个 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]。
(注意:真正的程序员可能会使用从零开始的索引。)
关于algorithm - 使用 BIT 计算反转，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11497502/