CODEWITHSUNDEEP
algorithmdata-structures
maplemaple
maplemaple

Reputation: 1715

Data structure which is efficient to add new number and count how many stored numbers smaller than some query number

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?

Upvotes: 3

Views: 336

Answers (1)

kaya3
kaya3

Reputation: 51063

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.

Upvotes: 3

Related Questions