given unsorted array of n integers, know can find total number of inversions using bit in o(n lg n)following method: count inversion bit
however possible if have query arbitrary range total # of inversions in o(lg n)?
a o(n lg n) pre-computation acceptable.
i have done research , seems n factor not avoidable... suggestions appreciated!
this not answer looking, have 2 suggestions.
first, not think bit right data structure use problem trying solve. bit's advantage maintains o(lg n) queryable prefix sum using o(lg n) per insertion. since aren't inserting once data structure completed, bit not advantageous (because use simple prefix sum array, queryable in o(1)).
second, have naive algorithm uses o(n2) time , space construct data structure can find range inversions in o(1) time:
first, construct (n x n) matrix mapping inversions, mat[i][j]=1 if i<j , arr[i] , arr[j] inverted. then, compute prefix sum across each row of matrix, mat[i][j] number of inversions involving arr[i] in range [i,j]. finally, compute suffix sum across each column, mat[i][j] total number of inversions in range [i,j].
for 0 n-2 j i+1 n-1 if(arr[j] > arr[i]) mat[i][j] = 1; 0 n-2 j i+1 n-1 mat[i][j] += mat[i][j-1]; j n-1 1 j-1 0 mat[i][j] += mat[i+1][j]; this takes o(n2) time , space, number of inversions in range can queried in constant time.
