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.