假设我有一个STL set <int> s和一个int x，我如何计算其中s少于的元素数x？
set <int> s
int x
s
x
我正在寻找一种O(log n)（或类似方法；比之合理地更好的方法O(n)）解决方案；
O(log n)
O(n)
我已经知道了std::distance(s.begin(), s.lower_bound(x))，但是O(n)我相信那是因为，sets不是随机访问的。
std::distance(s.begin(), s.lower_bound(x))
set
您需要的是“订单统计树”。从本质上讲，它是一种增强的（二进制搜索）树，支持附加操作rank(x)，该操作可为您提供键数小于或等于element的元素数量x。第14章，科门，雷森，里维斯特，斯坦；“算法简介”应为您提供算法背景。
rank(x)
网上也有一些实现。
