Длина объединения интервалов онлайн
Мне нужна структура данных, которая хранит набор интервалов и позволяет рассчитать длину их объединения.
Предположим, что на линии есть набор интервалов с целыми числами, заканчивающимися между 1 а также n, Первоначально он пуст, и к нему можно добавлять или удалять интервалы. После каждой операции нужно вычислить длину объединения всех интервалов в наборе.
Как можно реализовать это через дерево сегментов с помощью O(log n) время сложность для толкания, удаления и определения длины? Что следует хранить в узлах?
Решение
Хранения минимума и количества элементов, которые имеют минимальное значение в каждом узле, здесь достаточно. Добавление интервала эквивалентно добавлению 1 к диапазону, а удаление интервала эквивалентно добавлению -1 к диапазону. Длина союза составляет:
1. n если минимальное значение не равно нулю для корня дерева.
2. n — c, где c количество элементов с минимальным значением для корня дерева, если минимальное значение равно нулю.
Минимум не может быть отрицательным (любая точка всегда покрыта 0 или более интервалами).
Другие решения