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