How to find the kth smallest element within an interval of an array <p>Suppose I have an unsorted integer array a[] with length N. Now I want to find the kth smallest integer within a given interval a[i]-aj. Ex: I have an array a[10]={10,15,3,8,17,11,9,25,38,29}. Now I want to find the 3rd smallest element within [2,7] interval. The answer is 9. I know this can be done by sorting that interval. But this costs O(MlogM)(M=j-i+1) time. I also know that, this can be done by segment tree. But I can't understand how to modify it to handle such query.</p>