Find the number of values between i & j(given as input) in an unsorted array in O(1) time Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i&lt;k&lt;j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement is that the preprocessing should be $O(n)$ in both time and space.

I tried calculating an auxiliary array $B$ of size $M$ (where M is the maximum value in $A$) where $B[i]$ stores the number of elements smaller than $i$ in the given array. But for this the time and space complexities would be of order $O(M)$. Can one do better than that?
In $A$, $rank( A[i] ) = \left\vert\left\{ j \in A : -\infty &lt; j &lt; A[i] \right\}\right\vert $

So you could sort the array by putting each element at its rank (up to duplicates, which can also be counted with 2 range queries), so if you could answer queries like this in $O(1)$ time and $O(n)$ preprocessing time and space, you would have an $O(n)$ sorting algorithm.

The latter does exist of course, but only under certain constraints, eg on the range of values.