Блог пользователя Aritra741

Автор Aritra741, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.