Range median query in an array in O(1) time using preprocessing

Question

In classroom we learnt about RMQ to LCA to RMQ problems and how to support the operation range minimum query in O(1) time. As an exercise my professor has assigned me to support the operation : Range median query in O(n) space, O(n) preprocessing time and O(1) select time.

Let's say I have an array A that contains 8, 7, 9, 2, 6, 4, 5, 3. Given median(i, j) we should get the median between the ith and jth elements (inclusive) after sorting the array. A sorted is 2, 3, 4, 5, 6, 7, 8, 9. For example median(2,6) = A[4] = 6 (because median of 4, 5, 6, 7, 8 is 6).

I found other solutions that suggest using segment trees but the complexity is not O(1) in those cases. Is it possible to solve this problem in a similar manner that we solve the RMQ to LCA to RMQ problem?

What does median mean here? A[(i + j) / 2]? How do you resolve the median of an even number of items? (A[floor((i + j) / 2)] + A[ceil((i + j) / 2)]) / 2? — Paul S.
I haven't really slept lately, the array is meant to be sorted before we calculate for the median. If the number of the sub array is even then exactly as you said. — thelaw
if the sorting is not included in this problem, my previous comment is O(1) — Paul S.
I can't use normal sorting as the lower bound for sorting is O(nlogn). I need to use a preprocessing method that takes O(n) time as I mentioned. — thelaw

Helium_1s2 Helium_1s2 · Accepted Answer · 2018-06-25T03:31:57

One option would be to use a non-comparative sorting algorithm. Examples I know of being radix sort (O(wn), where w is the word size) and counting sort (O(n+k), where k is the maximum key value). Both of these are linear with respect to input size.

Then, you could just look up the correct position within the list, which is an O(1) operation. Both sorting methods are within your space requirements -- radix sort is O(n+k) and counting sort is O(k).

Range median query in an array in O(1) time using preprocessing

2 Answers