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