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.