Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

8:07p

Структура данных для хранения интервалов Всем привет!

Нужна структура данных, позволяющая эффективно:
1. хранить интервалы целых чисел (возможно наложенные друг на друга): Range={ int start, int end }
2. находить интервалы, содержащие определенную точку (тоже целое число)

Более детально:
1. интервалы всегда находятся внутри [0..99]
2. после нахождения определенного интервала:
2.1. либо мы оставим интервал нетронутым (редко)
2.2. либо разделим его на две части, выкинув несколько 2-3 числа в районе поиска (часто)
2.3. либо выкинем интервал вообще (часто)

Кажется, тривиальная проблема, но гугл пока ничего интересного не выдал.

Идеи?

Спасибо.