# Sorted unsigned integer intervals tree structure

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?

• 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. – Mr. Sigma. Dec 8 '18 at 12:12
• 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? – John L. Dec 8 '18 at 12:19
• @Apass.Jack Thanks for your note. I tried to update my question. – David Dec 8 '18 at 14:06
• Can you confirm that the order of insertion matters? 10–50 followed by 40–70 is different from 40–70 followed by 10–50. – John L. Dec 8 '18 at 14:17
• Yes, you're right. The order of insertion matters. – David Dec 8 '18 at 14:31

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)$$