c++ - C++ 集合：计数小于一个值的元素

Question

假设我有一个 STLset <int> s和一个int x，我如何计算其中s小于的元素数量x？

我正在寻找一个O(log n)（或类似的；任何比 合理更好的O(n)）解决方案；

我已经知道了std::distance(s.begin(), s.lower_bound(x))，但O(n)我相信那是，因为sets 不是随机访问。

Answer 1

您需要的是“订单统计树”。它本质上是一个增强的（二进制搜索）树，它支持额外的操作rank(x)，它为您提供与 element 具有更少或等于 key 的元素的数量x。第 14 章，Cormen、Leiserson、Rivest、Stein；“算法简介”应该为您提供算法背景。

网上也有一些实现。

Answer 2

我不认为这是可能的。您的 STL 集是基于树的结构，因此即使只是检查元素的存在也是 O(log n)。您的树的节点不会将其子分支的大小存储在任何字段中（据我所知），因此计算具有某些属性的节点所需的操作数不能直接遵循用于构建树的规则超过这些节点的数量。由于您事先不知道有多少节点的值小于 x，因此最坏情况下的性能是所有节点都小于 x 时，这意味着 O(n) 最坏情况复杂度。即使值 x 在树中，您也需要 O(log n) 操作来找到该节点，但随后需要访问其所有左侧后代以计算它们，所以复杂度取决于匹配节点的数量，在最坏的情况下是 O(n)。也许在树的节点中有额外的数据，可以做得更好。

Answer 3

作为对我的评论的跟进：使用红黑二叉搜索树（而不是集合），如果每个节点存储以该节点为根的节点数（每次插入/删除节点时更新），那么您可以在“节点数大于/小于 X”的统计数据非常快。