Изменения

Элементы односвязного списка состоят из вершин <tex>-</tex> вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:

'''node''' i = lvl.head <font color=darkgreen>// Перебор всех элементов lvl</font>

В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на хвост конец списка на первом уровне.

res = res.next() <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font>

Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{listskip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом

find(listskip.head(), key)

Для того, чтобы вставить Добавить элемент в список с пропусками, нужно запустить рекурсивную функцию, которая можно следующим образом:# Начинаем вставку в самом верхнем уровне# На каждом из уровней найдёт позициюуровне находим место, где должен был стоять куда надо вставить элемент# Если мы на первом уровне <tex>-</tex> вставляем элемент и кидаем монету. Если это первый уровеньвыпал «Орёл», то просто вставляем возвращаем ссылку на только что вставленный элемент в список, а также бросаем монетку и иначе возвращаем результат. ''null''# Если же это мы не самый нижний уровеньна первом уровне, то вызываем рекурсивно вызываем функциюот нижнего уровня, которая обрабатывает следующий уровень. Если в результате броска монетки и если нам вернулась ссылка на элемент <tex>-</tex> вставляем его на нижнем текущем уровне выпал «Орёл», то вставляем элемент в список текущего уровня, а также и снова кидаем монетку и возвращаем результат броска. Если же выпала «Решка»монету, то иначе просто возвращаем такой же результат. Нужно также обработать случай, когда на всех уровнях выпал «Орёл». В таком случае надо создать новый верхний уровень и вставить в него текущий элемент, а также присвоить списку с пропусками ссылку на начало самого верхнего списка.''null'' ====Псевдокод====

Для того, чтобы удалить Алгоритм удаления элемента выглядит следующим образом:# Начинаем удалять элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом верхнего уровня# Если мы на первом уровне, подобно поиску, найдёт позицию, где должен был стоять и нашли элемент. Во время рекурсии если это самый нижний уровень, <tex>-</tex> то просто удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то рекурсивно вызовем функцию от уровня # Иначе спускаемся ниже, а и также удалим удаляем элемент в текущем уровне. После удаления элемента могло так получитьс текущего уровня, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на начало самого верхнего уровня.если он есть====Псевдокод====

* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex><tex>-</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списком используем по факту всего один список.* <tex>\{1, 0\}</tex> {{---}} зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>\inftyO(n)</tex>.

Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. Очевидно, что оба запроса На каждый запрос мы обрабатываем отвечаем онлайн за <tex>O(\log{n})</tex>, при этом нет никакой необходимости знать запросы заранеевремени.