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?

  • $\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. Dec 8 '18 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. Dec 8 '18 at 12:19
  • $\begingroup$ @Apass.Jack Thanks for your note. I tried to update my question. $\endgroup$ – David Dec 8 '18 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. Dec 8 '18 at 14:17
  • $\begingroup$ Yes, you're right. The order of insertion matters. $\endgroup$ – David Dec 8 '18 at 14:31

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.


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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