nig*_*ler 5 c++ algorithm data-structures
给定1到10 ^ 5(非重复)范围内的数字输入流,我们需要能够在每个点处告知先前遇到多少小于此的数字.
我试图在C++中使用set来维护已经遇到的元素,然后接受upper_bound当前数字的集合.但是upper_bound给了我元素的迭代器,然后我再次遍历集合或使用std::distance,它再次是线性的.
我可以维护一些其他数据结构或遵循其他算法以更有效地完成此任务吗？
编辑:找到一个与fenwick树相关的旧问题,这在这里很有帮助.顺便说一句,我现在使用段树从@doynax评论中提示,解决了这个问题.