Range inversion queries

Правка en1, от 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

Теги #data structures

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский box 2020-09-14 03:54:52 491 Initial revision (published)