Редактирование: Список с пропусками

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях, номера которых меньше <tex>i</tex>.
+
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях с номерами меньших <tex>i</tex>.
  
 
==Построение==
 
==Построение==
Строка 11: Строка 11:
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
+
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
  
 
====Псевдокод====
 
====Псевдокод====
  
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head} \ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
+
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
  
Элементы односвязного списка вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
+
Элементы односвязного списка <tex>-</tex> вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
* <tex>\mathtt{next}</tex> ссылка на следующий элемент списка на данном уровне
+
* <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент списка
* <tex>\mathtt{key}</tex> ключ, который хранится в данной вершине
+
* <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине
* <tex>\mathtt{down}</tex> ссылка на соответственный элемент, лежащий уровнем ниже
+
* <tex>\mathtt{down}</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже
  
    '''struct''' node:
+
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>.
        '''node''' next, down
 
        '''K''' key
 
 
 
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>,
 
  
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
  
     '''list''' build_lvl('''list''' lvl)                   
+
     '''list''' build_lvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
         '''list''' next_lvl
+
         '''list''' next_lvl  
        next_lvl.head.down = lvl.head
+
         '''node''' i = lvl.head                       <font color=darkgreen>// Перебор всех элементов lvl</font>
        next_lvl.tail.down = lvl.tail
+
         '''while''' (i != ''null'') '''and''' (i != lvl.tail)
         '''node''' i = lvl.head.next.next                     
+
             next_lvl.push_back(node(i.key, i)<font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
        '''node''' cur = next_lvl.head
+
             i = i.next.next                     <font color=darkgreen>// Переход к следующему чётному элементу</font>
         '''while''' i <tex>\neq</tex> ''null'' '''and''' i.next <tex>\neq</tex> ''null''
 
             cur.next = node(key, i, cur.next)                 <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key, ссылками down на нижний и next на следующий элемент</font>
 
            cur = cur.next
 
             i = i.next.next                                   <font color=darkgreen>// Переход к следующему чётному элементу</font>
 
 
         '''return''' next_lvl  
 
         '''return''' next_lvl  
  
 
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
 
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
  
     '''list''' skip_list('''list''' l):
+
     '''list''' skip_list ('''list''' l):
         '''list''' lvl                                               <font color=darkgreen>// Построение первого уровня</font>
+
         '''list''' lvl = build_lvl(l)                <font color=darkgreen>// Построение первого уровня</font>
         '''node''' i = l.head
+
         '''while''' lvl.size > 2                    <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
        '''node''' j = lvl.head
 
        '''while''' j <tex>\neq</tex> l.tail
 
            i.next = node(j.key, ''null'', j.next)
 
            i = i.next
 
            j = j.next
 
        '''while''' lvl.size > 2                   
 
 
             lvl = build_lvl(lvl)                       
 
             lvl = build_lvl(lvl)                       
         '''return''' lvl                                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
+
         '''return''' lvl                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
  
 
==Операции над структурой==
 
==Операции над структурой==
 
===Поиск элемента===
 
===Поиск элемента===
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
+
 
 +
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]]
 +
 
 +
Алгоритм поиска элементе в списке с пропусками состоит из следующих операций:
 
# Начинаем поиск элемента в самом верхнем уровне
 
# Начинаем поиск элемента в самом верхнем уровне
 
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
 
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
# Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину
+
# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> прекратить поиск и вернуть ссылку на текущую вершину
  
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
+
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на хвост списка на первом уровне.
  
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет <tex>k</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{1/k}</tex> раз элементов больше, чем уровнем выше. В таком случае время поиска элемента <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
+
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
  
 
====Псевдокод====
 
====Псевдокод====
Строка 71: Строка 60:
 
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
 
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
 
   
 
   
     '''T''' find('''node''' res, '''K''' key)
+
     '''T''' find ('''node''' res, '''K''' key)
         '''while''' res.key < key                                         
+
         '''while''' res.key < key                                        <font color=darkgreen>// Пока значение вершины меньше ключа</font>
             res = res.next                                        
+
             res = res.next()                                      <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font>
         '''if''' res.down = ''null''                                   <font color=darkgreen>// Если мы находимся на первом уровне</font>
+
         '''if''' res.down = ''null''                                         <font color=darkgreen>// Если мы находимся на первом уровне</font>
             '''return''' res                                       <font color=darkgreen>// Мы нашли искомый элемент</font>
+
             '''return''' res                                             <font color=darkgreen>// Мы нашли искомый элемент</font>
         '''return''' find(res.down, key)                           <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
+
         '''return''' find(res.down, key)                                 <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
  
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
+
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{list}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
  
     find(skip.head, key)
+
     find(list.head(), key)
  
 
===Вставка элемента===
 
===Вставка элемента===
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
+
Добавить элемент в список можно следующим образом:
# Начинаем вставку на самом верхнем уровне
+
# Начинаем вставку в самом верхнем уровне
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
+
# На каждом уровне находим место, куда надо вставить элемент
# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
+
# Если мы на первом уровне <tex>-</tex> вставляем элемент и кидаем монету. Если выпал «Орёл», то возвращаем ссылку на только что вставленный элемент, иначе возвращаем ''null''
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
+
# Если мы не на первом уровне, то вызываем рекурсивно функцию от нижнего уровня, и если нам вернулась ссылка на элемент <tex>-</tex> вставляем его на текущем уровне и снова кидаем монету, иначе просто возвращаем ''null''
 
 
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 
 
 
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
 
  
 
====Псевдокод====
 
====Псевдокод====
Функция <tex>\mathtt{insert} \ </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
 
 
    '''node''' insert('''node''' res, '''K''' key)
 
        '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
 
            res = res.next                                   
 
        '''node''' down_node
 
        '''if''' res.down = ''null''
 
            down_node = ''null''
 
        '''else'''
 
            down_node = insert(res.down, key)
 
        '''if''' down_node <tex>\neq</tex> ''null'' '''or''' res.down = ''null''                <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font>
 
            res.next = node(key, down_node, res.next)
 
            '''if''' coin_flip() = ''head''                              <font color=darkgreen>// Если выпал «Орёл»</font>
 
                '''return''' res.next
 
            '''return''' ''null''
 
        '''return''' ''null''
 
 
Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в список с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию
 
 
    '''function''' insert_element('''list''' skip, '''K''' key)
 
        '''node''' res = insert(skip.head, key)
 
        '''if''' res <tex>\neq</tex> ''null''
 
            '''list''' lvl
 
            lvl.head.next = node(key, res, lvl.tail)
 
            skip = lvl
 
  
 
===Удаление элемента===
 
===Удаление элемента===
Алгоритм удаления элемента выглядит следующим образом:
+
Для того, чтобы удалить элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом уровне, подобно поиску, найдёт позицию, где должен был стоять элемент. Во время рекурсии если это самый нижний уровень, то удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем уровне. После удаления элемента могло так получить, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на начало самого верхнего уровня.
# Начинаем удалять элемент с верхнего уровня
 
# Переходим к следующему элементу, пока значение следующего элемента меньше ключа
 
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
 
====Псевдокод====
 
Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.
 
 
 
    '''function''' delete('''node''' res, '''K''' key)
 
        '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
 
            res = res.next
 
        '''if''' res.down <tex>\neq</tex> ''null''
 
            delete(res.down, key)
 
        '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
 
            res.next = res.next.next
 
 
 
Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O(k \cdot n^{1/k})</tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
 
 
 
Для того, чтобы удалить элемент <tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:
 
 
 
    delete(skip.head, key)
 
  
 
==Использование нечестной монеты==
 
==Использование нечестной монеты==
Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{1/p} {n} \right)</tex> <tex>(</tex>на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{1/p} {n}</tex><tex>)</tex>.
+
Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex> (на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{\frac{1}{p}} {n}</tex>).  
 
 
Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>\left\{ p, q \right\}</tex>, при котором функция <tex>\dfrac{1}{x} \log_{1/x} {n}</tex> принимает минимальное значение. Производная этой функции равна <tex>-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}</tex>. При <tex>x = \dfrac{1}{e}</tex> производная равна нулю, вторая производная в точке <tex>x_0 = \dfrac{1}{e}</tex> больше <tex>0</tex>, значит <tex>x_0</tex> <tex>-</tex> точка минимума. Значит при распределении <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> почти невозможно, поэтому на практике лучше всего использовать честную монету.
 
  
 
Для крайних распределений:
 
Для крайних распределений:
* <tex>\{0, 1\}</tex> <tex>O(n)</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
+
* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex> <tex>-</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списком используем по факту всего один список.
* <tex>\{1, 0\}</tex> зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.
+
* <tex>\{1, 0\}</tex> {{---}} зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.
  
 
==Применение==
 
==Применение==
  
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:
+
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
* Следующий элемент достаётся за <tex>O(1)</tex> (при условии, что у нас есть ссылка не текущий)
+
* Следующий элемент достаётся за <tex>O(1)</tex>
 
* Легко модифицировать под различные задачи
 
* Легко модифицировать под различные задачи
  
===Нахождение всех отрезков, покрывающих данную точку===
+
===Нахождение всех интервалов, покрывающих данную точку===
 
 
 
{{Задача
 
{{Задача
|definition = Пусть у нас есть запросы двух видов:
+
|definition = Есть <tex>q</tex> запросов двух видов:
# Добавить отрезок <tex>[L, R]</tex>
+
# Добавить интервал <tex>[L, R]</tex>
# Для заданной точки <tex>x</tex> вычислить количество отрезков, которые её покрывают.  
+
# Задана точка <tex>x</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.next.key - 1]</tex>, <tex>[l.next.key, r.key]</tex> и <tex>[r.key + 1, R]</tex> и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex> части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна <tex>l.next.key</tex> или <tex>r.key</tex>. Итого время обработки запроса <tex>O(\log{n})</tex>.
+
Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. На каждый запрос мы отвечаем онлайн за <tex>O(\log{n})</tex> времени.
 
 
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>.
 
  
 
==См. также==
 
==См. также==
Строка 177: Строка 113:
 
*[[Поисковые структуры данных]]
 
*[[Поисковые структуры данных]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 +
*[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками
  
 
==Источники информации==
 
==Источники информации==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: