C++设置: counting elements less than a value

Question

假设我有一个 STL set <int> s和 int x , 如何计算 s 中的元素个数小于 x ?

我正在寻找 O(log n) (或类似的；任何比 O(n) 更好的东西)解决方案；

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

Answer 1

您需要的是“订单统计树”。它本质上是一个增强的(二分搜索)树，支持附加操作 rank(x)，它为您提供具有小于或等于元素 x 的键的元素数量。第 14 章，Cormen、Leiserson、Rivest、Stein； “算法简介”应该为您提供算法背景。

web 上也有一些实现.