Number of elements less than X

Question

I need a structure that can quickly (log N) count the number of elements smaller than a certain value/modify values. I know it is easy to do with an R-B tree or similar, but I wanted to save time by using STL, which already implements these trees. However, I can't find any function that would do what I need - is it even possible, possibly using a trick of some sort? I know it requires storing the number of elements in every subtree, which it might not do normally.

Answer 1

You can do this with a simple sorted vector or array:

std::vector<int> V;
// (fill V with values)
std::sort(V.begin(), V.end());

int numValsLessThan5 = std::lower_bound(V.begin(), V.end(), 5) - V.begin();
int numValsLessThanOrEqualTo5 = std::upper_bound(V.begin(), V.end(), 5) - V.begin();

upper/lower_bound has logarithmic complexity when used on containers which support random access.