Suppose we are going to insert n numbers(may have duplicates), how would you design a data structure that supports the following functions in O(log n) time. The value range is very large.
int insert(int val) // return the index(how many numbers that are smaller than val) of the val
int find(int k) // return the kth minimal value.
void delete(int val) // delete the value
For offline algorithm(We can know all the values before), using binary index tree will be enough. But without that, how can we implement it?
