0
$\begingroup$

The goal is to store sorted unsigned integer intervals that can overlap only in the boundaries, e.g., |0–10|10–50|100–110|110–200|. This structure will be created by some insert operations (the order matters) in the start and than queried by a lot of queries. The query is specified by interval and the result is all intervals from structure that has at least a partial overlap.

There is no need to delete inserted data (delete operation), but the new inserted interval can overwrite the existing ones. Please consider the following example.

  1. |0–10|10–50|100–110|110–200|
  2. insert: 40–70
  3. |0–10|10–40|40–70|100–110|110–200|
  4. insert: 105–115
  5. |0–10|10–40|40–70|100–105|105–115|115–200|

What structure do you recommend?

Improve this question
$\endgroup$
7
  • $\begingroup$ IMO, its better to think about $B+$ trees. In $B+$ trees you would get keys sorted from left leaves to right. They are usually preferred for range queries. $\endgroup$
    – Mr. Sigma.
    Commented Dec 8, 2018 at 12:12
  • $\begingroup$ Welcome to Computer Science! "Is it right to think about ...?" That sounds ambiguous enough to possibly prevent readers to become confident to post a succinct answer. Can you list the desired qualities of (the insert operation on) the data structure? What are the typical use cases such as many insertions and few queries or few insertions and many queries? $\endgroup$
    – John L.
    Commented Dec 8, 2018 at 12:19
  • $\begingroup$ @Apass.Jack Thanks for your note. I tried to update my question. $\endgroup$
    – David
    Commented Dec 8, 2018 at 14:06
  • $\begingroup$ Can you confirm that the order of insertion matters? 10–50 followed by 40–70 is different from 40–70 followed by 10–50. $\endgroup$
    – John L.
    Commented Dec 8, 2018 at 14:17
  • $\begingroup$ Yes, you're right. The order of insertion matters. $\endgroup$
    – David
    Commented Dec 8, 2018 at 14:31

2 Answers 2

Reset to default
0
$\begingroup$

Interval trees seem like a natural candidate. The Wikipedia page has links to implementations in various languages. You can overwrite an existing interval by querying its endpoints, then removing the resulting intervals on the left and right, and then adding back the truncated intervals together with the new one.

Improve this answer
$\endgroup$
1
0
$\begingroup$

As Mr. Sigma suggest you, you need to use a B+ tree structure. time to insert new value is $\Theta(th)=\Theta(t\log _{t}n)$

Check this one for implementation

https://www.geeksforgeeks.org/b-tree-set-1-insert-2/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.