This is a question from careercup:

You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};

Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.

E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.

## Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.

Among the proposed solutions, I think the best is quickselect ( query time complex: O(b-a), space complex: no extra space, preprocessing time complex: none)

I am confused by this questions since there seems no way to improve the query time complex by doing any preprocessing.

Anybody have any insight on how to use preprocessing to improve the query TC? Thanks.