algorithm - Range 查询反转次数 O(lg N)

Question

给定一个包含 n 个整数的未排序数组，我知道我可以按照以下方法在 O(N lg N) 中使用 BIT 找到求逆的总数:Count Inversion by BIT

但是，如果我必须在 O(lg N) 中查询任意范围内的总反转数，是否有可能？

O(N lg N) 的预计算是可以接受的。

我做了一些研究，似乎 N 因素是不可避免的......任何建议，将不胜感激!

Answer 1

这不是您正在寻找的答案，但我有两个建议。

首先，我认为 BIT 不是用于您要解决的问题的正确数据结构。 BIT 的优点是它维护一个 O(lg n) 的可查询前缀和，每次插入仅使用 O(lg n)。由于您不会在数据结构完成后插入，因此 BIT 没有优势(因为您可以使用简单的前缀和数组，它在 O(1) 中是可查询的)。

其次，我有一个天真的算法，它使用 O(n²) 的时间和空间来构造一个可以在 O(1) 时间内找到范围反转的数据结构:

首先，构造一个映射反转的 (n X n) 矩阵，使得 mat[i][j]=1仅当i<j和 arr[i]和 arr[j]是倒置的。然后，计算该矩阵每一行的前缀和，使得 mat[i][j]是涉及 arr[i] 的反转次数在 [i,j] 范围内.最后，计算每列的后缀和，使得 mat[i][j]是 [i,j] 范围内的反转总数.

for i from 0 to n-2
  for j from i+1 to n-1
    if(arr[j] > arr[i])
      mat[i][j] = 1;
for i from 0 to n-2
  for j from i+1 to n-1
    mat[i][j] += mat[i][j-1];
for j from n-1 to 1
  for i from j-1 to 0
    mat[i][j] += mat[i+1][j];

这明明是O(n²)的时间和空间，但是在常数时间内可以查询任意范围内的反转次数。