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.

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3668 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | ainta | 3318 |

9 | Itst | 3239 |

10 | apiadu | 3238 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 204 |

2 | Monogon | 201 |

2 | SecondThread | 201 |

4 | vovuh | 189 |

5 | Um_nik | 188 |

6 | pikmike | 186 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 174 |

9 | pashka | 169 |

10 | -is-this-fft- | 166 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2020 21:03:50 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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.

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?

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.

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.

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.Can you elaborate implementation details?

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

Multiset Implementation