Preprocessing arrays for fast sorted-subarray queries

Suppose you have an array of \( n \) real numbers (or other totally ordered values that you can compare but not treat as small integers). You want to answer queries that specify a contiguous subarray and return the sorted sequence of values within that subarray. Without any preprocessing you could query a subarray of length \( k \) in time \( O(k\log k) \), by pulling out the subarray and then comparison sorting it. With preprocessing, how much better can we do?

The obvious answer would be to sort the input, and replace each real number by an integer, its position in the sorted sequence. Doing this would allow us to use integer sorting algorithms to handle each query. This works particularly well for long queries (longer than \( n^{\epsilon} \) for some \( \epsilon\gt 0 \)), because then you can use radix sort to answer the query in linear time. But it is still somewhat problematic for shorter queries, where we don't have time to set up and then take down the big arrays used by radix sort, and where other integer sorting algorithms are both less practical than radix sort and slower than linear time.

So here's a trick that works better. For each \( i \) from \( 1 \) to \( \log^* n \), divide the array into sub-arrays of size \( 2^{2^i} \). Sort these subarrays (by merging the smaller subarrays from the next smaller value of \( i \)) and, for each element, write down its position in the sorted subarray; this is a \( 2^i \)-bit binary number. Then, for each element of the whole big array, write down one number, the concatenation of these numbers for all the subarrays. (It works best if the bigger subarrays get more-significant bits of the concatenation.) That way, each of the original inputs gets an index number that is still only \( O(\log n) \) bits long. By doing the recursive array partition top-down instead of bottom-up you can make the number of bits at most \( 2\log n \), and by using a larger base than 2 you can make it at most \( (1+\epsilon)\log n \) for any \( \epsilon\gt 0 \).

Then, to handle any query subarray of length \( k \), decompose the query into at most two of the subarrays of the recursive decomposition above that are both of length \( O(k^2) \). Mask off the higher order bits of the index numbers within those subarrays so that the remaining number of bits is \( O(\log k) \), small enough that radix sort can be used to sort these numbers in linear time. Merge the two sorted subarrays to give the answer to the query.

The time to preprocess the input is \( O(n\log n) \), unsurprising since we have to comparison sort somewhere. But the space for the resulting data structure is only \( O(n) \), and it allows sorted-subarray queries in time linear in the length of the subarray.

---

Comments: