algorithm - Range 查询倒数 O(lg N)

Question

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

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

AO(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和反转。然后，计算该矩阵每一行的前缀和，即范围中涉及的反转数。最后，计算每列的后缀总和，这就是 range 中的反转总数。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 ² ) 的时间和空间，但是可以在恒定时间内查询任意范围内的反演次数。