390
правок
Изменения
Нет описания правки
* Следующий элемент достаётся за <tex>O(1)</tex>
* Легко модифицировать под различные задачи
===Нахождение всех интервалов, покрывающих данную точку===
Список с пропусками используют для решение одной из классических задач <tex>-</tex> нахождения количество интервалов, которые покрывают данную точку. Более подробное условие задачи: пусть у нас есть поле, координаты которого <tex>-</tex> любые (возможно вещественные) числа, а также задано два типа запросов:
# Добавить интервал <tex>[L, R]</tex>
# Задана точка <tex>x</tex>. Найти количество интервалов, которые покрывают данную точку
Список с пропусками позволяет решать данную задачу онлайн за <tex>O(\log{q})</tex> времени, где <tex>q</tex> <tex>-</tex> количество запросов. В отличии от дерева отрезков, для которого требуется, чтобы координаты были целыми числами в небольшом диапазоне, списку с пропусками не важно, какого типа координаты, главное, чтобы их можно было сравнивать.
Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. Очевидно, что оба запроса мы обрабатываем за <tex>O(\log{n})</tex>, при этом нет никакой необходимости знать запросы заранее.
==См. также==
