Data structure/algo for fast insertion and counting-CodePudding

I'm looking for a data structure/algorithm that allows both logarithmic insertion of elements into data structure, and logarithmic counting of elements in data structure that are smaller than a given value.

For instance, std::set<int> allows logarithmic insertion, and logarithmic iter = std::upper_bound(..., value) but then distance(iter, set.begin()) is linear...

Can it be done using C STL containers?

CodePudding user response：

There is a way, unfortunately only for GNU C . Called Policy based data structure.

I'll show basics of usage.

#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;

int main() {
    indexed_set s;
    s.insert(1);
    s.insert(5);
    s.insert(10);
    s.insert(20);
    s.insert(21);

    cout << s.order_of_key(10) << '\n';
}

order_of_key returns the number of values in a set that are strictly smaller than the value passed.

Further information: https://codeforces.com/blog/entry/11080