How to find the sum to the kth element of a sorted submatrix from l to r?

Question

Problem:
We gave an array A[] size N Now we have asked Q queries, each query consists of three integers l,r,k where:

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

Now we want to know the sum of the element k sorted submatrix from l to r .
For instance:
Let N=6 and an array element 5,1,7,4,6,3
And Q=1 , where l,r,k will be like 2,5,3 .
then the sub-array from index 2 to index 5 be {1,7,4,6}
after sorting it becomes like {1,4,6,7} so the sum up to k=3 terms is (1+4+6)=11
therefore the answer is 11 .

I tried to sort each submatrix and then summarize, in the worst case, Q*N*log(N) time complexity is required.
Please help find the best solution within the time complexity of less than Q*N in the worst case.

Answer 1

One approach would be to pre-execute using mergesort with a modification so that we keep a copy of all sorted intermediate results.

This preprocessing takes O (nlogn).

Suppose we started with 32 elements. Now we have:

• 16 sorted item lists
• 8 sorted item lists
• 4 sorted item lists
• 2 sorted 16 item lists
• 1 list of sorted 32 items.

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

Then, faced with a query from l to r, we can identify log (n) pre-processed lists, which together will cover all the elements from l to r.

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

Answer 2

If O (Q)> = O (log N):

Sorting the initial indexes of arrays in the sort order of their elements, for example:

 values: [50, 10, 20, 40, 30] -> [10, 20, 30, 40, 50] indices: [#0, #1, #2, #3, #4] -> [#1, #2, #4, #3, #0] 

Then, for each query, scan the sorted indices from left to right and add the values ​​of the first k elements whose indices are within the range ([l, r]). The complexity will be O (QN + N log N) = O (QN) - again, provided that O (Q)> = O (log N).

There is a way to improve this by first sorting the ranges of queries and then running all the queries in a single scan of sorted indexes, but there is no way to predict how this will affect complexity without knowing anything special about the length of the ranges.