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

Question

我正在解决一个问题，我意识到我需要一个数据结构，具有以下属性，但即使经过几个小时的搜索也找不到。我相信STL库太丰富了，不可能没有这个，因此在这里询问。

1. 能够在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()，但我无法在O(log(n))时间内完成第3个要求。它需要O(n)。

有什么提示可以轻松完成它吗？

- Anoop

---

请不要在没有评论的情况下给出负面评价！！ - Anoop

我没有我的可靠指南书，但如果你能找到'Skiena, Steven S'的《算法设计手册》，一定要去获取。这是我查找算法的首选来源。 - ntroncos

我相信哈希表应该对所有操作都具有log(n)的时间复杂度，但我不确定。 - R Nar

@RNar，哈希表在插入和删除方面具有O(1)的时间复杂度，但在给定范围内查找元素数量的时间复杂度为O(n)。此外，重复值也是一个问题。 - Anoop

如果我想起来了，这些就是我推荐的内容：相似问题，概要，STL 我已经将它们加入了书签。 - ntroncos

multi_set有一个count成员，其时间复杂度为O(log(N) + K)，其中N是范围大小，K是匹配数。 - TemplateRex

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

- behzad.nouri

Answer 2

尽管标准库确实功能齐备，但我认为您在其中不会找到具有这些特定要求的任何内容。正如您所指出的那样，类似集合的结构返回非随机访问迭代器——要提供随机访问（或者像您需要的某种距离函数）将引入相当复杂的问题。

您可以通过实现可索引的跳表来实现目标，该跳表提供O(log(n))的插入、删除和索引查找，这在此处https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist中有所描述。

实现指南可在此处提供http://cg.scs.carleton.ca/~morin/teaching/5408/refs/p90b.pdf。

- Jack O'Reilly

---

跳表是这个任务的正确数据结构。"计算范围内元素数量"任务变成了两个O(log(n))查找。 - Borealid

Answer 3

这项任务的两种明显数据结构是跳表（Jack O'Reilly已经提到）和某个变体的顺序统计树（Behzad提到但没有真正解释）。一个顺序统计树在每个节点中存储一段额外信息。你可以存储任何数量的不同元素，但我发现最容易理解的是每个节点存储其左子树中元素的数量。当您插入元素时，您会在遍历树下降到左侧时增加计数。由于你只修改你要遍历的节点，所以这不会改变O(log N)的插入。当重新平衡时，必须相应地进行调整（但是，你只修改旋转时已经修改的节点中的计数，因此（再次）不会影响总体复杂度。当您需要找到一个元素到另一个元素的距离时，只需找到两个节点，每个节点具有O(log N)的复杂度。你通过从根节点初始化索引，然后从那里更新它来找到每个元素的索引（向左下降时减去计数，向右下降时添加）。

- Jerry Coffin

Answer 4

你应该能够通过标准的或略微修改过的B树来实现这一点。

通常情况下，B树实现的大多数标准操作的时间复杂度为O(log(n))。

- Erix

Answer 5

这种方法并不是最节省空间的，时间复杂度为O(3n)，但它满足上述插入、删除和距离标准。以下使用了链表、映射和无序映射。

链表用于维护顺序。通常按顺序插入列表的时间是线性的，但通过一个键到列表迭代器的映射，我们可以在常数时间内插入。将有序数据存储在列表中的优点是它使用随机访问迭代器，这意味着您可以获得一个常数时间的std::distance调用。

映射用于获取在列表中插入节点的提示。这是通过为给定的键创建一个新的映射条目，然后将迭代器减1来完成的。这个新迭代器的值给出了我们在链接列表中适当的插入位置。

无序映射为我们提供了o(1)的随机访问列表迭代器查找，使我们能够获得o(logn)的删除和距离时间。

class logn
{
public:
    using list_it = std::list<int>::iterator;

    void insert(int i)
    {
        const bool first = list.empty();
        auto original_it = map.insert({i,list.end()}).first; // o(logn)
        auto hint = original_it;
        if (!first)
            --hint; 
        umap[i] = list.insert(hint->second,i);  // o(1)
        original_it->second = umap[i]; 
    }

    void remove(int i)
    {
        auto it = umap.find(i); // o(1)
        list.erase(it->second); // o(1)
        umap.erase(it);         // o(1)
        map.erase(map.find(i)); // o(logn)
    }

    list_it get(int i) const
    {
        return umap.find(i)->second;
    }

    unsigned int distance(int lower, int upper) const
    {
        return std::distance(get(lower), get(upper));
    }

private:

    std::list<int> list;
    std::unordered_map<int, list_it> umap;
    std::map<int, list_it> map;

};

- makar