Problem:

We have given an array A[] of size N. Now we have given Q queries, each queries consist of three integer l,r,k where:

1<=l<=r<=N
1<=k<=(r-l+1)
1<=N,Q<=10^5

Now,we want to find out the sum upto the k element of the sorted sub-array from l to r.

For example:

N=6 and array element be 5,1,7,4,6,3 And Q=1 where l,r,k be as 2,5,3. then sub-array from index 2 to index 5 be {1,7,4,6} after sorting it becomes as {1,4,6,7} so sum upto k=3 term is equal to (1+4+6)=11 so answer is 11 .

I have tried using sorting of each sub-array and then sum, it takes Q*N*log(N) time complexity in worst case. Please help to find any better solution within time complexity less than Q*N in worst case.