c++ - 在整数输入流中遇到的先前较小元素的计数？

Question

给定一个从 1 到 10^5(不重复)的数字输入流，我们需要能够在每个点上判断出之前遇到过多少比这个数字小的数字。

我尝试使用 C++ 中的集合来维护已经遇到的元素，然后在集合上取 upper_bound 作为当前数字。但是 upper_bound 给了我元素的迭代器，然后我必须再次遍历集合或使用 std::distance，这又是线性时间。

我是否可以维护一些其他数据结构或遵循一些其他算法以更有效地完成此任务？

编辑:发现了一个与芬威克树相关的旧问题，在这里很有帮助。顺便说一句，我现在已经使用从@doynax 评论中获取提示的线段树解决了这个问题。

How to use Binary Indexed tree to count the number of elements that is smaller than the value at index?

Answer 1

无论您使用的是什么容器，将它们作为有序集输入是个好主意，这样在任何时候我们都可以只获取元素索引或迭代器以了解它之前有多少个元素。