5

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.

riv
  • 6,846
  • 2
  • 34
  • 63
  • 1
    There's [Boost Intrusive](http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive.html), but as far as I know, there's no good way with the STL. – David Eisenstat Apr 23 '14 at 20:15
  • Do you need fast insertions and deletions too? – Brian Bi Apr 23 '14 at 20:16
  • If you restrict yourself to G++, it has an [order-statistic tree implementation](http://stackoverflow.com/questions/11230734/c-stl-order-statistic-tree). That is of course if you need online insertion and deletion, otherwise you can use a sorted array. If you have a compact universe or you can compress it using preprocessing, you can also use a [binary-indexed tree](http://stackoverflow.com/questions/21780668/best-data-structure-algorithm-for-insert-delete-rank-select-queries/23233101#23233101) – Niklas B. Apr 23 '14 at 20:52
  • Yes, I need insertions/deletions too. Guess I'll just stick with writing R-B code myself since I can't use non-standard libraries. – riv Apr 23 '14 at 23:37
  • Treaps are much faster and easier to code, by the way – Niklas B. Apr 24 '14 at 07:48

1 Answers1

4

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.

Sneftel
  • 40,271
  • 12
  • 71
  • 104