Коротко — надёжный путь: сегментное дерево с подсчётом покрытий (lazy count) над массивом элементарных отрезков, полученных либо сжатием координат, либо имплицитно на фиксированном диапазоне. Ниже — компоненты, инварианты, операции и сложности.
Компоненты
- Массив уникальных координат (при сжатии): $X[\mathrm{0..}N]$ отсортирован, элементарный отрезок $i$ = $[X[i],X[i+1))$.
- Узел сегдерева, покрывающий индексный диапазон $[L,R)$ элементарных отрезков, с полями:
- $cnt$ — целочисленный счётчик прямого покрытия этого узла (сколько интервалов полностью покрывают весь узел).
- $len$ — суммарная длина покрытой части в этом узле (в единицах координат).
- указатели/индексы на левый и правый дочерние узлы.
- Для имплицитного дерева вместо массива $X$ хранится числовой диапазон $[A,B)$ и в узле — длина сегмента $B-A$.
Инварианты
1. $cnt\ge 0$. Если $cnt>0$, то весь сегмент узла полностью покрыт и $len=$ длина сегмента.
2. Если $cnt=0$, то $len=left.len+right.len$ (для листа — $len=0$ если нет покрытия).
3. Узел всегда отражает суммарную покрытую длину своих элементарных отрезков.
Операции
- Вставка интервала $[l,r)$:
1. Привести $l,r$ к индексам элементарных отрезков (сжатие) либо работать с числовым диапазоном.
2. Вызвать update(node, ql, qr, delta=+1): при полном покрытии узла увеличить $cnt$ на $+1$; затем recompute $len$: если $cnt>0$ то $len=$ длина сегмента, иначе $len=left.len+right.len$.
- Удаление интервала $[l,r)$:
аналогично вставке, но с $delta=-1$. (Нужно гарантировать удаление только существующей копии; для этого храните multiset/хэш по id интервала.)
- Запрос суммы покрытия на отрезке $[a,b)$:
1. Привести к индексам и выполнить query(node, ql, qr): если узел полностью внутри запроса вернуть $len$; если частично — рекурсивно суммировать результаты дочерей при учёте $cnt$ (но по инварианту при $cnt>0$ узел уже полностью покрыт).
Реализация основных правил обновления (push-up):
- При входе в узел после изменения детей:
- если $cnt>0$ тогда $len=$ длина сегмента узла;
- иначе $len=left.len+right.len$ (если лист и $cnt=0$ — $len=0$).
Сложности
- Пусть $N$ — число элементарных отрезков (после сжатия), либо $U$ — размер числового диапазона для имплицитного дерева.
- Время вставки/удаления/запроса: $O(\log N)$ (со стандартным бинарным деревом) или $O(\log U)$ для имплицитного сегдерева.
- Память: $O(N)$ для полного дерева, или $O(k)$ для динамически выделяемого дерева (где $k$ — число созданных узлов).
- Построение массива координат (сжатие) из $m$ операций: $O(m\log m)$; после этого каждая операция — $O(\log N)$.
Замечания и практические детали
- Используйте представление полуинтервалов $[l,r)$ для однозначности. Для включительно/исключительно конвертируйте вручную.
- Для удаления по идентификатору храните хэш-таблицу, сопоставляющую id интервала его $(l,r)$ в сжатых индексах.
- Если нужна строго гарантия $O(\log n)$ по числу интервалов $n$ и без известного набора координат, можно использовать динамический сегдерев (implicit) на диапазоне значений типа 64-бит; время будет $O(\log U)$, где $U$ — диапазон координат (например $2^{64}$).
Итого: сегментное дерево с полем счётчика покрытий и хранением длины покрытой части обеспечивает вставку, удаление и запрос суммы покрытий за $O(\log N)$ при сжатых координатах (или $O(\log U)$ для имплицитного).