范围查询O(lg N)中的反转次数

Question

给定n个整数的未排序数组,我知道我可以在这个方法之后找到使用BIT在O(N lg N)中的反转总数: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和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 ² ) 时间和空间，但可以在常数时间内查询任意范围内的反转次数。