std::multimap + sum on range

Revision ru2, by metal4people, 2021-07-25 22:33:13

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian metal4people 2021-07-25 22:33:13 2 Мелкая правка: 'example:\n- Query(' -> 'example:\n\n- Query('
ru1 Russian metal4people 2021-07-25 22:31:41 648 Первая редакция (опубликовано)