15

我正在尝试解决以下问题：正在将数字插入容器中。每次插入一个数字时，我都需要知道容器中有多少元素大于或等于当前插入的数字。我相信这两种操作都可以以对数复杂度完成。

我的问题： C++ 库中是否有可以解决问题的标准容器？我知道std::multiset可以在对数时间内插入元素，但是如何查询呢？或者我应该实现一个数据结构（例如二叉搜索树）来解决它？

4

5 回答 5

4

好问题。我认为 STL 中没有任何东西可以满足您的需求（前提是您必须有对数时间）。正如 aschepler 在评论中所说，我认为最好的解决方案是实现 RB 树。你可以看看 STL 源代码，特别是stl_tree.h看看你是否可以使用它的一部分。

更好的是，看看：（C++ 中的排名树）

其中包含实现的链接：

（http://code.google.com/p/options/downloads/list）

于 2013-07-02T15:39:49.630 回答
1

是的，您应该使用多重集来计算对数复杂度。但是计算距离是个问题，因为 set/map 迭代器是双向的，而不是 RandomAccess，std::distance 的复杂度为 O(n)：

multiset<int> my_set;
...
auto it = my_map.lower_bound(3);
size_t count_inserted = distance(it, my_set.end()) // this is definitely O(n)
my_map.insert(make_pair(3);

您的复杂性问题很复杂。这是一个完整的分析：

如果您希望每次插入的复杂度为 O(log(n))，则需要一个已排序的结构作为一个集合。如果您希望结构在添加新项目时不重新分配或移动项目，则插入点距离计算将为 O(n)。如果事先知道插入大小，则在排序容器中不需要对数插入时间。您可以插入所有项目然后排序，它与集合中的 n * O(log(n)) 插入一样多。唯一的选择是使用一个专用的容器，比如加权 RB-tree。根据您的问题，这可能是解决方案，或者确实有些矫枉过正。

  • 使用multisetand distance，你在插入时是 O(n.log(n)) （是的，n 次插入 * log(n) 每个插入时间），在距离计算上是 O(nn)，但计算距离非常快。
  • 如果你事先知道插入的数据大小（n）：使用一个向量，填充它，排序它，返回你的距离，你是 O(n.log(n))，而且很容易编码。
  • 如果您事先不知道 n，那么您的 n 可能很大，每个项目都占用大量内存，因此您不能进行 O(n.log(n)) 重新分配：那么您有时间重新编码或重新使用一些非标准代码，你真的必须满足这些复杂性期望，使用专用容器。还可以考虑使用数据库，在内存中维护它可能会遇到问题。
于 2013-07-02T16:09:30.660 回答
1

这是在 C++ 中使用基于策略的数据结构的快速方法：

存在一种称为有序集的东西，它允许您在 O(logN) 时间内插入/删除元素（以及 std::set 必须提供的几乎所有其他功能）。它还提供了另外 2 个功能：查找第 K 个元素和**查找第 X 个元素的排名。问题是这不允许重复:(

不过不用担心！我们将使用单独的索引/优先级映射重复项，并定义一个新结构（称为 Ordered Multiset）！我在下面附上了我的实现以供参考。

最后，每次你想找到大于 x 的元素数时，调用函数 upper_bound（小于或等于 x 的元素数）并从有序多重集的大小中减去这个数字！

注意：PBDS 使用大量内存，所以这是一个约束，我建议使用二叉搜索树或 Fenwick 树。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

struct ordered_multiset { // multiset supporting duplicating values in set
    int len = 0;
    const int ADD = 1000010;
    const int MAXVAL = 1000000010;
    unordered_map<int, int> mp; // hash = 96814
    tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> T;

    ordered_multiset() { len = 0; T.clear(), mp.clear(); }

    inline void insert(int x){
        len++, x += MAXVAL;
        int c = mp[x]++;
        T.insert((x * ADD) + c); }

    inline void erase(int x){
        x += MAXVAL;
        int c = mp[x];
        if(c) {
            c--, mp[x]--, len--;
            T.erase((x*ADD) + c); } }

    inline int kth(int k){        // 1-based index,  returns the
        if(k<1 || k>len) return -1;     // K'th element in the treap,
        auto it = T.find_by_order(--k); // -1 if none exists
        return ((*it)/ADD) - MAXVAL; } 

    inline int lower_bound(int x){      // Count of value <x in treap
        x += MAXVAL;
        int c = mp[x];
        return (T.order_of_key((x*ADD)+c)); }

    inline int upper_bound(int x){      // Count of value <=x in treap
        x += MAXVAL;
        int c = mp[x];
        return (T.order_of_key((x*ADD)+c)); }

    inline int size() { return len; }   // Number of elements in treap
};

用法：

    ordered_multiset s;
    for(int i=0; i<n; i++) {
        int x; cin>>x;
        s.insert(x);
        int ctr = s.size() - s.upper_bound(x);
        cout<<ctr<<" ";
    }

输入（n = 6）：10 1 3 3 2
输出：0 1 1 1 3

时间复杂度：每个查询/插入 O(log n)

参考：mochow13 的 GitHub

于 2020-11-18T02:21:57.353 回答
0

听起来像是一个案例count_if-尽管我承认这并不能解决对数复杂度的问题，但这需要排序类型。

vector<int> v = { 1, 2, 3, 4, 5 };
int some_value = 3;

int count = count_if(v.begin(), v.end(), [some_value](int n) { return n > some_value; } );

编辑完成以修复 lambda 函数的语法问题

于 2013-07-02T15:01:01.050 回答
0

如果整个数字范围足够小（大约几百万），则可以使用Fenwick 树相对容易地解决此问题。

尽管Fenwick 树不是 STL 的一部分，但它们都非常易于实现且节省时间。更新和查询的时间复杂度O(log N)和常数因子都很低。

您在对另一个问题的评论中提到，您在比赛中需要这个。Fenwick 树是竞争性编程中非常流行的工具，并且通常很有用。

于 2016-04-15T21:40:35.540 回答