Range inversion queries

Revision en1, by box, 2020-09-14 03:54:52

Currently the best known complexities for querying the number of inversions in a range of a static array is $$$O(n+m)$$$ space $$$O(n\sqrt{m})$$$ time for offline; $$$O(n\sqrt{m})$$$ space same time for online. Is there any proof of these lower bounds (a proof that it's impossible to solve range inversion query in linear times polylog time), or can range inversion queries theoretically be done with lower time complexity?

source

Tags #data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English box 2020-09-14 03:55:33 30 Tiny change: 'n\n[source](http://o' -> 'n\n[source for current time complexities](http://o'
en1 English box 2020-09-14 03:54:52 491 Initial revision (published)