overwrite's blog

By overwrite, history, 5 weeks ago, In English

How to design a Segment Tree which will give me the sum of the first k numbers?

It seems easy but I don't know how to handle the duplicate elements.

Thanks.

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Do you mean k smallest numbers on the segment? Is k fixed or does it vary from query to query?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Actually I didn't specify it, sorry about it.

    I'm looking for at most k numbers so that the sum is minimum. So If there are only positive numbers, I take nothing. And yes k is fixed, it is same for all queries. And not in segment, in whole array.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't understand it. What is the problem statement? You have just one query of computing the minimum sum with at most k numbers? Why not sort them and take k smallest until they are positive?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm trying to solve this problem. The editorial mentioned that I need to use segment tree to get that — at most k elements with maximum/minimum sum.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You just store the set of numbers in the segment tree. Suppose you have an array cnt[x] which means the number of times that x appears in your set. Then you just build segment tree on this array.

          In order to do it you either will have to write a compressed segment tree (the one with pointers), or just pre-compress the numbers.

          I suggest you google something like "using segment tree as a set", I don't really know the keywords.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I handled big numbers with index compression that was not the problem for me. I was not able to handle duplicate elements in the tree though.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you elaborate implementation details?

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

If you want to get the sum of constant-k-smallest numbers onlinely you can also do this

Multiset Implementation