在O（log n）时间中找到给定范围内的元素数的数据结构是什么？ [英] What data structure to find number of elements in a given range in O(log n) time?

问题描述

我正在解决一个问题，但我意识到我需要一个具有以下属性的数据结构，但即使经过数小时的谷歌搜索也无法找到一个。我相信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. 插入任何元素（应该可以包含重复的元素）在 O（log（n））时间


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


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

1. Insert any element(should be able to contain repetetive ones) in O(log(n)) time
2. Remove an element in O(log(n)) time as well.
3. 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);
}

这篇关于在O（log n）时间中找到给定范围内的元素数的数据结构是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！