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.↵
↵
↵
↵
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.↵
↵
int 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?
↵
↵
↵
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.↵
↵
int 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?
