how to find sum up to kth element of sorted sub-array from l to r?

Question

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:
Let 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.

Answer 1

One approach would be to preprocess by using mergesort with the modification that we keep a copy of all the sorted intermediate results.

This preprocessing takes O(nlogn).

Suppose we started with 32 elements. We would now have:

• 16 sorted 2 element lists
• 8 sorted 4 element lists
• 4 sorted 8 element lists
• 2 sorted 16 element lists
• 1 sorted 32 element list.

We can also precompute the prefix sum of each of these lists in O(nlogn).

Then when faced with a query from l to r, we can identify log(n) of the preprocessed lists that together will cover all elements from l to r.

We can then use binary search to find the value such that there are exactly k smaller elements in the identified lists, and use the prefix sums to calculate the sum.