Range Query the number of inversion in O(lg N)

Question

Given an unsorted array of n integers, I know I can find the total number of inversions using BIT in O(N lg N)following this method: Count Inversion by BIT

However is it possible if I have to query an arbitrary range for the total # of inversions in O(lg N)?

A O(N lg N) pre-computation is acceptable.

I have done some research and seems the N factor is not avoidable... Any suggestions would be appreciated!

Phlyctena

what does "query an arbitrary range for the total # of inversions" mean ? – Conjunction

query any range [l,r], where 0<= l <= r <= n-1, return the total # of inversions within this range – Phlyctena

To anyone interested, I saw in some place that somebody used something called "Wavelet Matrix" to work this thing out...This structure is too complicated for me now so I skip it directly... – Phlyctena

You can do offline queries using MO's algorithm and BIT – Valeda

Answer 1

This is not the answer for which you are looking, but I have two suggestions.

First, I do not think that BIT is the right data structure to use for the problem you are trying to solve. BIT's advantage is that it maintains an O(lg n) queryable prefix sum using only O(lg n) per insertion. Since you aren't inserting once your data structure is completed, BIT is not advantageous (because you could use a simple prefix sum array, which is queryable in O(1)).

Second, I have a naive algorithm that uses O(n²) time and space to construct a data structure that can find range inversions in O(1) time:

First, construct an (n X n) matrix mapping the inversions, so that mat[i][j]=1 only if i<j and arr[i] and arr[j] are inverted. Then, compute a prefix sum across each row of this matrix, so that mat[i][j] is the number of inversions involving arr[i] in the range [i,j]. Finally, compute a suffix sum across each column, so that mat[i][j] is the total number of inversions in the range [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];

This clearly takes O(n²) time and space, but the number of inversions in any range can be queried in constant time.

Presidency

How to use "prefix sum array" to query "total number of inversions in a range?" :o – Phlyctena

@Phlyctena After the preprocessing, the value of mat[i][j] is the number of inversions between i and j. – Presidency