CODEWITHSUNDEEP
algorithmsortingsumdynamic-programming
user7534168
user7534168

Reputation: 91

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

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.

Upvotes: 5

Views: 498

Answers (2)

shinobi
shinobi

Reputation: 361

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

Sort the original array indices by the sorting order of their elements, for instance:

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 left to right, and add the values of the first k elements that you encounter whose indices are within range ([l, r]). The complexity will be O(QN + N log N) = O(QN) -- again, provided that O(Q) >= O(log N).

There's a way to improve on this by sorting the query ranges first, and then execute all queries in a single scan of the sorted indices, but there's no way to predict how this will affect complexity, short of knowing something special about the lengths of the ranges.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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.

Upvotes: 3

Related Questions