I'm solving a problem and I realized I am need of a data structure with following properties but cant find one even after few hours of googling. I believe STL library is too rich to not have this one hence asking here.
O(log(n)) timeO(log(n)) time as well.O(log(n)) time..If I were to write it from scratch, for part 1 and 2, I would use a set or multiset and I would modify their find() method(which runs in O(log(N)) time) to return indices instead of iterators so that I can do abs(find(a)-find(b)) so I get the count of elements in log(N) time. But unfortunately for me, find() returns and iterator.
I have looked into multiset() and I could not accomplish requirement 3 in O(log(n)) time. It takes O(n).
Any hints to get it done easily?
Though not part of STL, you may use Policy-Based Data Structures which are part of gcc extensions; In particular you may initialize an order statistics tree as below. The code compiles with gcc without any external libraries:
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
int main()
{
tree<int, /* key */
null_type, /* mapped */
less<int>, /* compare function */
rb_tree_tag, /* red-black tree tag */
tree_order_statistics_node_update> tr;
for(int i = 0; i < 20; ++i)
tr.insert(i);
/* number of elements in the range [3, 10) */
cout << tr.order_of_key(10) - tr.order_of_key(3);
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments