Range Request the number of inversions in O (log N)

Question

Given an unsorted array of n integers, I know that 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 that I should request an arbitrary range for the total number of inversions in O (log N)?

AO (N lg N) pre-calculation is acceptable.

I did some research and it seems that the N-factor cannot be avoided ... We appreciate any suggestions!

Answer 1

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

First of all, I don’t think BIT is the correct data structure used for the problem you are trying to solve. The advantage of BIT is that it supports the O (log n) requested prefix sum, using only O (log n) for each insert. Since you do not insert as soon as your data structure is completed, BIT will not be profitable (because you can use the simple array of prefix sums that is requested in O (1)).

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

First, we construct an (n X n) matrix representing inversions, so that mat[i][j]=1 only if i<j and arr[i] and arr[j] inverted. Then calculate the sum of the prefix for each row of this matrix, so mat[i][j] is the number of inversions involving arr[i] in the range [i,j] . Finally, calculate the suffix sum for each column, so 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 obviously takes time and space O (n ² ), but the number of inversions in any range can be requested in constant time.