Hello everybody!
Is there a predefined data structure in C++ that allows you to insert numbers (maybe even dublicate keys) and effectively count the amount of numbers greater or less than a given value?
Now I'm using a recursive implementation of Red Black Tree — Here in original (Java) and Here translated to C++ with count_greater implemented.
One idea would be using std::lower_bound
in std::map
and then std::distance
from map.begin() to the result iterator.
ordered set
http://mirror.codeforces.com/blog/entry/11080
Can use map<int, int>, where key is number, value is count of dublicates, and insert in ordered set pair e.g. make_pair(number, mp[number]++)
And use order_of_key. Time comlexity
O(log(n)2)O(log(n))Why not ?
Because of using map<int, int> :/ Keys can be dublicate
But it is ...
Ok, all right, thanks
Treap
ext_map will support find_by_order and order_of_key. Just try it.