### overwrite's blog

By overwrite, history, 5 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. Comments (8)
 » 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 →   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?
 » 5 weeks ago, # | ← Rev. 3 →   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(); } };