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.


|0–10|10–50|100–110|110–200|
insert: 40–70
|0–10|10–40|40–70|100–110|110–200|
insert: 105–115
|0–10|10–40|40–70|100–105|105–115|115–200|


What structure do you recommend?
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.