xblwyc's blog

By xblwyc, history, 8 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it