Return to Question

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.

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?

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?

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 in the start and than queried by a lot of queries.

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?

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.

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?

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|.

I'm curious only about the insert operation. The main problem is probably the division of the existing intervals (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|

In the end, there are queries against this sorted intervals structure. Is it right to think about modification of some AVL or Red-Black tree?

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 in the start and than queried by a lot of queries.

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?