Hi everyone,

I'm searching for data structure that would be like std::multimap + possibility to compute range sum on values in log(N) time. Erase by keys or changing values should also be in-place.

Let's say I've inserted next key-value pairs: (1,2), (2,3), (3,4), (4, 5), queries for example:

• Query(2), ans: 1*2 = 2;
• Query(4), ans: 1*2 + 2*2 = 5;
• Query(6), ans: 1*2 + 2*3 + 3*1 = 11;
• Query(10), ans: 1*2 + 2*3 + 3*4 + 1*5 = 25;

Currently I do it in O(n) by traversing the map.

Please help me and thank you in advance, Taras

P.S. If you know similar problem, I'd be grateful if you can share.