3

I want to find an efficient data structure that can handle the following use case.

I can add new elements to this data structure, e.g. I call add() API, add([2,3,4,5,3]), then this data structure stores [2,3,3,4,5]. I can query some target and return how many numbers smaller than this target. e.g. query(4), return 3 (since one 2 and two 3). And the frequencies of calling add and query are in the same order.

Firstly, I think of segment tree, however, the input number can be anyone in int value, space will be O(2^32)

Could you give me some advice about which data structure should I use?

Arvind Kumar Avinash
  • 71,965
  • 6
  • 74
  • 110
maplemaple
  • 1,297
  • 6
  • 24

1 Answers1

3

You can do this using an order statistic tree, which is a kind of binary search tree where each node also stores the cardinality of its own subtree. Inserting into an order statistic tree still takes O(log n) time, because it's a binary search tree, although the insert operation is a little more complicated because it has to keep the cardinalities of each node up-to-date.

Computing the number of members less than a given target also takes O(log n) time; start at the root node:

  • If the target is less than or equal to the root node's value, then recurse on the left subtree.
  • Otherwise, return the left child's cardinality plus the result of recursing on the right subtree.

The base case is that you always return 0 for an empty subtree.

kaya3
  • 47,440
  • 4
  • 68
  • 97