### overwrite's blog

By overwrite, history, 4 weeks ago,

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.

• -20

 » 4 weeks ago, # |   +3 Do you mean k smallest numbers on the segment? Is k fixed or does it vary from query to query?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 4 weeks ago, # ^ |   0 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?
•  » » » » 4 weeks ago, # ^ |   0 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.
•  » » » » » 4 weeks ago, # ^ |   0 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.
•  » » » » » » 4 weeks ago, # ^ |   0 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.
•  » » » » » » 4 weeks ago, # ^ |   0 Can you elaborate implementation details?
 » 4 weeks ago, # | ← Rev. 3 →   0 If you want to get the sum of constant-k-smallest numbers onlinely you can also do this Multiset Implementationbool ERASE(multiset &S, int x) { multiset::iterator it = S.find(x); if (it != S.end()) { S.erase(it); return true; } return false; } struct summin { int k; ll cnt = 0, sum = 0; multiset L, R; multiset::iterator it; summin (int k = 0) : k(k) {} void add(int x) { sum += x; L.insert(x); if (L.size() > k) { x = *L.rbegin(); sum -= x; ERASE(L, x); R.insert(x); } cnt = L.size(); } void rmv(int x) { if (ERASE(L, x)) sum -= x; else ERASE(R, x); if (L.size() < k && R.size() > 0) { x = *R.begin(); sum += x; L.insert(x); ERASE(R, x); } cnt = L.size(); } };