box's blog

Range inversion queries
By box, history, 4 years ago, In English

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 for current time complexities

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry if I am wrong but I found one paper related to Range Inversion Counting right here. Hope it help you something :D

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I didn't read the entire paper yet, but it looks like it concerns finding inversions of the entire array faster, rather than finding inversions of ranges.

    → Reply