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

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

Внимание! Вы не авторизовались на сайте. Ваш 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                       
        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{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
Строка 85: Строка 74:
 
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
 
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
 
# Начинаем вставку на самом верхнем уровне
 
# Начинаем вставку на самом верхнем уровне
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
+
# Пока следующих элемент следующего элемента меньше ключа <tex>-</tex> идём по списку вправо.
# Если мы на первом уровне вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
+
# Если мы на первом уровне <tex>-</tex> вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>.
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе ''null''. Если мы были не на первом уровне и нам вернули ''null'' возвращаем его без броска монетки.
+
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе <tex>-</tex> ''null''. Если мы были не на первом уровне и нам вернули ''null'' <tex>-</tex> возвращаем его без броска монетки.
 
 
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 
  
Заметим, что вставка элемента <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'', если на монете выпала «Решка».
+
Функция <tex>\mathtt{insert}</tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпал не «Орёл».
  
     '''node''' insert('''node''' res, '''K''' key)
+
     '''node''' insert ('''node''' res, '''K''' key)
         '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
+
         '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.next <tex>\neq</tex> ''null''
             res = res.next                                  
+
             res = res.next
        '''node''' down_node
 
 
         '''if''' res.down = ''null''
 
         '''if''' res.down = ''null''
             down_node = ''null''
+
             res.next = node(key, ''null'', res.next)
        '''else'''
+
            '''if''' random(0, 1) > 0.5
             down_node = insert(res.down, key)
+
                '''return''' res.next
         '''if''' down_node <tex>\neq</tex> ''null'' '''or''' res.down = ''null''                <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font>
+
             '''return''' ''null''
             res.next = node(key, down_node, res.next)
+
        node i = insert(res.down, key)
             '''if''' coin_flip() = ''head''                              <font color=darkgreen>// Если выпал «Орёл»</font>
+
         '''if''' i <tex>\neq</tex> ''null''
 +
             res.next = node(key, i, res.next)
 +
             '''if''' random(0, 1) > 0.5
 
                 '''return''' res.next
 
                 '''return''' res.next
 
             '''return''' ''null''
 
             '''return''' ''null''
Строка 112: Строка 100:
  
 
Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в список с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию
 
Для того, чтобы вставить элемент с ключом <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>-</tex> то просто удаляем элемент
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
+
# Иначе спускаемся ниже и также удаляем элемент с текущего уровня, если он есть
 
====Псевдокод====
 
====Псевдокод====
Функция <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>.
  
 
==Применение==
 
==Применение==
  
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:
+
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
Строка 159: Строка 123:
 
* Легко модифицировать под различные задачи
 
* Легко модифицировать под различные задачи
  
===Нахождение всех отрезков, покрывающих данную точку===
+
===Нахождение всех интервалов, покрывающих данную точку===
  
 
{{Задача
 
{{Задача
|definition = Пусть у нас есть запросы двух видов:
+
|definition = Поступают запросы двух видов:
# Добавить отрезок <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>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем), а также идём с самого верхнего уровня и до нижнего и если два элемента на каком-либо уровне находятся между <tex>L</tex> и <tex>R</tex>, то прибавляем <tex>1</tex> к отрезку, иначе спускаемся вниз. Когда нам приходит запрос второго типа <tex>-</tex> на каждом уровне находим такие два элемента, что <tex>x</tex> лежит между ними, и к ответу прибавляем значение на данном отрезке. Итого оба запросы мы выполняем за <tex>O(\log{n})</tex>.
 
 
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>.
 
  
 
==См. также==
 
==См. также==
Строка 177: Строка 138:
 
*[[Поисковые структуры данных]]
 
*[[Поисковые структуры данных]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 +
*[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками
  
 
==Источники информации==
 
==Источники информации==

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

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

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

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