在O(log n)时间内,在给定范围内查找元素数量的数据结构是什么？

Question

我正在解决一个问题,我意识到我需要一个具有以下属性的数据结构,但即使经过几个小时的谷歌搜索也无法找到.我相信STL库太丰富了,所以没有这个问题.

1. 插入任何元素(应该能包含的repetetive的)的O(log(n))时候
2. 同时删除元素O(log(n)).
3. 如果我想查询范围[a,b]中的元素数量,我应该及时得到这个数量O(log(n)).

如果我是从头开始编写的,对于第1部分和第2部分,我会使用set或者multiset我会修改他们的find()方法(O(log(N))及时运行)来返回索引而不是迭代器,这样我就可以这样做了 abs(find(a)-find(b)),我得到了元素的数量在log(N)时间内.但不幸的是,对我来说,find()返回和迭代器.

我已经调查过multiset(),我无法及时完成要求3 O(log(n)).需要O(n).

有任何提示可以轻松完成吗？

Answer 1

虽然不是STL的一部分,但您可以使用基于策略的数据结构,它是gcc扩展的一部分; 特别是,您可以初始化订单统计树,如下所示.代码编译时gcc没有任何外部库:

#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);
}