在O（log n）时间中找到给定范围内的元素数的数据结构是什么？

本文介绍了在O（log n）时间中找到给定范围内的元素数的数据结构是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在解决一个问题，但我意识到我需要一个具有以下属性的数据结构，但即使经过数小时的谷歌搜索也无法找到一个。我相信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.

插入任何元素（应该可以包含重复的元素）在 O（log（n））时间

删除 O（log（n））中的元素时间也是如此。

如果我想查询[a，b]范围内的元素数量，我应该将其计入 O（log（n））时间。

Insert any element(should be able to contain repetetive ones) in O(log(n)) time

Remove an element in O(log(n)) time as well.

If i want to query for the number of elemenes in range [a,b], I should get that count in O(log(n)) time..

如果我要从零开始编写，对于第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); }