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