Count of previously smaller elements encountered in an input stream of integers?

Question

Given an input stream of numbers ranging from 1 to 10^5 (non-repeating) we need to be able to tell at each point how many numbers smaller than this have been previously encountered.

I tried to use the set in C++ to maintain the elements already encountered and then taking upper_bound on the set for the current number. But upper_bound gives me the iterator of the element and then again I have to iterate through the set or use std::distance which is again linear in time.

Can I maintain some other data structure or follow some other algorithm in order to achieve this task more efficiently?

EDIT : Found an older question related to fenwick trees that is helpful here. Btw I have solved this problem now using segment trees taking hints from @doynax comment.

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

Answer 1

Regardless of the container you are using, it is very good idea to enter them as sorted set so at any point we can just get the element index or iterator to know how many elements are before it.