xblwyc's blog

By xblwyc, history, 5 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?

Read more »

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