a[]lengthのソートされていない整数配列があるとしNます。a[i]-a[j]ここで、指定された間隔( )内で k 番目に小さい整数を見つけたいと考えています1 <= i <= j <= N。例: 配列がありa[10]={10,15,3,8,17,11,9,25,38,29}ます。a[2]-a[7]今度は、間隔内で 3 番目に小さい要素を見つけたいと思います。答えは 9 です。これは、その間隔をソートすることで実行できることがわかっています。しかし、これにはO(Mlog(M))( M = j - i + 1) 時間がかかります。また、これはセグメントツリーで実行できることは知っていますが、そのようなクエリを処理するためにそれを変更する方法がわかりません。