Обсуждение участника:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\frac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
 
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\frac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
 +
 +
=== Псевдокод ===
 +
<code>
 +
'''int''' interpolationSearch(a : '''int[]''', key : '''int''') <font color=green> // a должен быть отсортирован </font>
 +
  left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) </font>
 +
  right = a.length - 1 <font color=green> // правая граница поиска </font>
 +
 +
  '''while''' a[left] < key '''and''' key < a[right]
 +
    mid = left + (key - a[left]) * (right - left) / (a[right] - a[left]) <font color=green> // индекс элемента, с которым будем проводить сравнение </font>
 +
    '''if''' a[mid] < key
 +
      left = mid + 1
 +
    '''else if''' a[mid] > key
 +
      right = mid - 1
 +
    '''else'''
 +
      '''return''' mid
 +
 +
  '''if''' a[left] == key
 +
    '''return''' left
 +
  '''else if''' a[right] == key
 +
    '''return''' right
 +
  '''else'''
 +
    '''return''' -1 <font color=green>// если такого элемента в массиве нет </font>
 +
</code>
  
 
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
 
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
Строка 37: Строка 60:
  
 
Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>(\frac{1}{2}\log_2 N)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени.
 
Осталось создать <tex>O(\sqrt N)</tex> таблиц {{---}} по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых <tex>(\frac{1}{2}\log_2 N)^2 = O(\log^2 N)</tex>. Для каждого блока в <tex>B_i</tex> необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за <tex>O(1)</tex>, затратив на предподсчёт <tex>O(\sqrt N \log^2 N)</tex> времени.
 +
 +
  
 
=== Результат ===
 
=== Результат ===

Версия 15:34, 16 июня 2015

Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера) — применяется для решения за [math]\langle O(N),O(1) \rangle[/math] времени специального случая задачи [math]RMQ[/math] (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для решения задачи [math]LCA[/math].


Задача:
Дан массив [math]A[1 \ldots N][/math] целых чисел, соседние элементы которой отличаются на [math]\pm 1[/math]. Поступают онлайн запросы вида [math](l, r)[/math], для каждого из которых требуется найти минимум среди элементов [math]A[l], A[l + 1], \ldots, A[r] [/math].


Алгоритм

Данный алгоритм основывается на методе решения задачи [math]RMQ[/math] с помощью разреженной таблицы (sparse table, ST) за [math]\langle O(N \log N),O(1) \rangle[/math].

Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность [math]A_i[/math] на блоки длины [math]\frac{1}{2}\log_2 N[/math]. Для каждого блока вычислим минимум на нём и определим [math]B_i[/math] как позицию минимального элемента в [math]i[/math]-ом блоке.

Псевдокод

int interpolationSearch(a : int[], key : int)  // a должен быть отсортирован 
  left = 0  // левая граница поиска (будем считать, что элементы массива нумеруются с нуля) 
  right = a.length - 1  // правая граница поиска 

  while a[left] < key and key < a[right]
    mid = left + (key - a[left]) * (right - left) / (a[right] - a[left])  // индекс элемента, с которым будем проводить сравнение 
    if a[mid] < key
      left = mid + 1
    else if a[mid] > key
      right = mid - 1
    else
      return mid

  if a[left] == key
    return left
  else if a[right] == key
    return right
  else
    return -1 // если такого элемента в массиве нет 

На новой последовательности [math]B_i[/math] построим разреженную таблицу. Теперь для ответа на запрос [math]RMQ[/math][math][i:j][/math], если [math]i[/math] и [math]j[/math] находятся в разных блоках, нам необходимо вычислить следующее:

  1. минимум на отрезке от [math]i[/math] до конца блока, содержащего [math]i[/math];
  2. минимум по всем блокам, находящимся между блоками, содержащими [math]i[/math] и [math]j[/math];
  3. минимум от начала блока, содержащего [math]j[/math], до [math]j[/math].

Ответом на запрос будет позиция меньшего из эти трёх элементов.

Части, из которых состоит ответ на запрос RMQ

Второй элемент мы уже умеем находить за [math]O(1)[/math] с помощью [math]И_i[/math] и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.

Минимум внутри блока

Утверждение:
Если две последовательности [math]x_i[/math] и [math]y_i[/math] таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. [math]\forall k: x_k = y_k + C[/math]), то любой запрос [math]RMQ[/math] даст один и тот же ответ для обеих последовательностей.

Таким образом, мы можем нормализовать блок, вычтя из всех его элементов первый. Тем самым мы значительно уменьшим число возможных типов блоков.

Утверждение:
Существует [math]O(\sqrt N)[/math] различных типов нормализованных блоков.
[math]\triangleright[/math]
Соседние элементы в блоках отличаются на [math]\pm 1[/math]. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен [math]\pm 1[/math]-вектором длины [math] (\frac{1}{2} \log_2 N) - 1[/math]. Таких векторов [math]2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)[/math].
[math]\triangleleft[/math]

Осталось создать [math]O(\sqrt N)[/math] таблиц — по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, которых [math](\frac{1}{2}\log_2 N)^2 = O(\log^2 N)[/math]. Для каждого блока в [math]B_i[/math] необходимо заранее вычислить его тип. Таким образом мы получили возможность отвечать на запрос минимума по любой части блока за [math]O(1)[/math], затратив на предподсчёт [math]O(\sqrt N \log^2 N)[/math] времени.


Результат

Итого, на предподсчёт требуется [math]O(N)[/math] времени и памяти, а ответ на запрос вычисляется за [math]O(1)[/math].

См. также

Источники информации

  • Bender, M.A., Farach-Colton, M. — The LCA Problem Revisited. LATIN (2000), с. 88-94