Aritra741's blog

[HELP] Sum of K-largest numbers in a range (using Merge Sort Tree?)
By Aritra741, history, 4 years ago, In English

I was wondering if it's possible to use Merge Sort Tree to find out the sum of K-largest numbers in a range. I've seen people solve it using Wavelet tree and Persistent Segment Tree. I failed to implement Merge Sort Tree in such a way that it solves the given task and now wondering if it's possible to do so.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

You can get the $$$k^{th}$$$ largest number, $$$num$$$, in that range using (another kind of) Merge Sort Tree..

Now, for the query of the sum of elements smaller than $$$num$$$, maintain the corresponding presums along with sorted arrays, and query in a similar way as normal merge sort tree queries.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can do it with merge sort tree. In merge sort tree at every node we store a sorted vector of given range. Now with that you can also maintain a vector of suffix sums for those sorted vectors. You can even store then as pairs. First store sorted vector and second store suffix sums.

Now first find the kTh largest element using first merge sort tree. Then you can find the sum of elements in the range greater than equal to k using second merge sort tree.

→ Reply