Online algorithm for racountinge inversions countingin range
Разница между en1 и en2, 146 символ(ов) изменены
I've been recently thinking about this problem:↵

Given array of n integers and q queries( l, r pairs ). For each query you need to count number of inversions( i, j pairs such that i < j and a[i] > a[j] )  in subarray from l to r. And you have to answer onthe queries online(you're not given all queries beforehand). ↵

I was able to come up with a solution that i'd describe below, but I'd like to know if it's possible to solve the problem with better 
time complexity.↵

So, my solution:↵

1) preprocessing↵

Let's divide our array into sqrt(n) blocks, each sized sqrt(n), and merge-sort elements inside these blockseach, counting number of inversions in each blockit. Then, for each pair of blocks, count number of inversions such that first element lies within first block and second lies within second block. We can do this using binary search, because each block is sorted already. After that, for each sqrt-block-range( [l, r] range such that l is a left border of one block and r is a right border of other block ) we'd find number of inversions in it by summing precalculated values( inversions in each block and inversions in pairs  of blocks). There are around n pairs and ranges so we can do all preprocessing in O(n * sqrt(n) * log(n)). ↵
We also need to build merge-sort tree 
on the array for queries.↵

2) queries↵

We already know answer for sqrt-block-range that lies within query range. Then we just need to count inversions that include elements outside sqrt-block-range. There no more than 2 * sqrt of themsuch elements, so we can do this usingwith binary search in merge-sort tree in O(sqrt(n) * log^2(n)), or in O(sqrt(n) * log(n)) if we usewith partial cascading.↵

Overall complexity: O((n + q) * sqrt(n) * log(n)) with partial cascading.↵

So what are your thoughts, can it be solved faster?↵

P.S. Sorry for my poor English.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский madn 2017-08-27 01:02:25 146 Final revision (published)
en1 Английский madn 2017-08-27 00:33:11 1812 Initial revision (saved to drafts)