我正在解决一个问题,但我意识到我需要一个具有以下属性的数据结构,但即使经过数小时的谷歌搜索也无法找到一个。我相信STL库太丰富了,所以没有这个,因此在这里询问。
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.
如果我要从零开始编写,对于第1部分和第2部分,我将使用 set 或 multiset ,然后修改其 find()方法(在 O(log(N))时间运行)返回索引而不是迭代器,以便我可以做 abs(find(a)-find(b)),这样我就可以得到log(N)时间的元素计数。但是对我来说不幸的是, find()返回并进行迭代。
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.
我研究了 multiset(),而我无法在 O(log(n))时间内完成要求3。花费 O(n)。
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?
推荐答案作为STL的一部分,您可以使用基于策略的数据结构 gcc扩展;特别是,您可以如下所述初始化订单统计树。该代码使用 gcc 进行编译,而没有任何外部库:
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); }更多推荐
在O(log n)时间中找到给定范围内的元素数的数据结构是什么?
发布评论