c++ - 严格小于给定数的元素数

Question

我想要一个数据结构，我想在其中插入元素 log(n) 时间并且元素应该在每次插入后在 ds 中排序。我可以为此使用多重集。

之后我想在 log(n) 时间内再次找到严格小于给定数字的元素数。是的，也存在重复项，需要考虑它们。例如，如果查询元素是 5 并且 ds 包含 {2, 2, 4, 5, 6, 8, 8} 那么答案将是 3(2, 2, 4) 因为这 3 个元素严格小于 5

我本可以使用 multiset 但即使我使用 upper_bound 我也将不得不使用以线性时间运行的距离方法。我怎样才能用 c++ STL 有效地实现这一点。我也不能用

Answer 1

你需要的数据结构是订单统计树:https://en.wikipedia.org/wiki/Order_statistic_tree

STL 没有，而且它们不是很常见，因此您可能需要自己动手。您可以在 Google 中找到代码，但我不能保证任何具体的实现。