6

I have a sorted array in which I find number of items less than particular value using binary search (std::upper_bound) in O(logn) time.
Now I want to insert and delete from this array while keeping it sorted. I want the overall complexity to be O(logn).

I know that using binary search tree or std::multiset I can do insertion, deletion and upper_bound in O(logn) but I am not able do get the distance/index (std::distance is O(n) for sets) in logarithmic time.

So is there a way to achieve what I want to do?

CCD
  • 73
  • 1
  • 5
  • Please amend your question - an array by itself is a linear data structure so that insertion or deletion wouldn't be cheap as you expected. – Fei Feb 09 '19 at 08:23
  • Depending on how big your data is a sorted array benefits from contiguity (being cache friendly) so you may get better performance if you just keep using the array, inserting/ deleting wherever `std::lower_bound`/`std::upper_bound` tells you. – Galik Feb 09 '19 at 08:29
  • This is not a duplicate of the suggested question, this is looking for better than `O(n)` index/distance. Though I think the requirements for insertion are mutually exclusive with that tbh. – Galik Feb 09 '19 at 08:44
  • What is the range for `n` and the values of the elements that you are supposed to store? – Kunal Puri Feb 09 '19 at 10:19
  • range upto 10^5 and values from -10^9 to 10^9 – CCD Feb 09 '19 at 10:31

2 Answers2

7

You can augment any balanced-binary-search-tree data structure (e.g. a red-black tree) by including a "subtree size" data-member in each node (alongside the standard "left child", "right child", and "value" members). You can then calculate the number of elements less than a given element as you navigate downward from the root to that element.

It adds a fair bit of bookkeeping, and of course it means you need to use your own balanced-binary-search-tree implementation instead of one from the standard library; but it's quite doable, and it doesn't affect the asymptotic complexities of any of the operations.

ruakh
  • 175,680
  • 26
  • 273
  • 307
1

You can use balanced BST with size of left subtree in each node to calculate distance

Prerna Jain
  • 21
  • 3