小于 X 的元素数

Question

我需要一个可以快速（记录 N）计算小于某个值/修改值的元素数量的结构。我知道用 RB 树或类似的树很容易做到，但我想通过使用 STL 来节省时间，它已经实现了这些树。但是，我找不到任何可以满足我需要的功能 - 甚至可能使用某种技巧吗？我知道它需要在每个子树中存储元素的数量，这可能不会正常执行。

Answer 1

您可以使用简单的排序向量或数组来完成此操作：

std::vector<int> V;
// (fill V with values)
std::sort(V.begin(), V.end());

int numValsLessThan5 = std::lower_bound(V.begin(), V.end(), 5) - V.begin();
int numValsLessThanOrEqualTo5 = std::upper_bound(V.begin(), V.end(), 5) - V.begin();

upper/lower_bound在支持随机访问的容器上使用时具有对数复杂度。