Изменения

Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.:

|definition = Поступают Пусть у нас есть запросы двух видов:# Добавить интервал отрезок <tex>[L, R]</tex>

Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с самого верхнего уровня , и до нижнего на каждом уровне мы ищем такие <tex>l</tex> и если два <tex>r</tex>, что значение <tex>l</tex> не больше <tex>L</tex>, а значение следующего за <tex>l</tex> элемента на каком-либо уровне находятся между уже больше <tex>L</tex>. Аналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next</tex> и <tex>r</tex> лежат полностью внутри отрезка <tex>[L, R]</tex>, то к самому отрезку <tex>[l.next, r]</tex> прибавляем <tex>1</tex> к отрезку , а сам отрезок <tex>[L, R]</tex> разбиваем на два и по отдельности прибавляем уже отрезки <tex>[L, l.key]</tex> и переходим к следующему элементу <tex>[r.next.key, R]</tex>. Допустим, что на том же каком-то уровнеу нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex>. части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза и только с одной стороны, иначе спускаемся внизпоскольку другая часть отрезка уже будет иметь чёткую границу, за которую он не переходит. Итого время обработки запроса <tex>O(\log{n})</tex>. Когда нам приходит запрос  Для запросов второго типа — на мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне находим такие два элементанайдём тот элемент, что значение которого не меньше точки <tex>x</tex> лежит между ними. Если такой элемент нашёлся, и то прибавляем к ответу прибавляем значение на данном отрезкеотрезку между найденным элементом и следующим. Итого оба запросы Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Очевидно, что данный тип запросов мы обрабатываем за <tex>O(\log{n})</tex>.