Алгоритм Фарака-Колтона и Бендера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Нафиг пробел добавили? — Отмена правки 10280 участника 192.168.0.2 (обсуждение))
(Григорий улучшил)
Строка 1: Строка 1:
'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи RMQ (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи LCA]].
+
'''Алгоритм Фарака-Колтона, Бендера (алгоритм Фарах-Колтона, Бендера)''' — применяется для решения за <tex>\langle O(N),O(1) \rangle</tex> времени специального случая задачи <tex>RMQ</tex> (поиск минимума на отрезке), в котором соседние элементы входной последовательности различаются на ±1. Может быть использован также для [[Сведение задачи LCA к задаче RMQ|решения задачи <tex>LCA</tex>]].
  
'''Вход:''' последовательность <tex>a_i</tex> длины <tex>N</tex>, соседние элементы которой отличаются на ±1.<br/>
+
{{Задача
'''Выход:''' ответы на онлайн запросы вида «позиция минимума на отрезке <tex>[i:j]</tex>».
+
|definition = Дан массив <tex>A[1 \ldots N]</tex> целых чисел, соседние элементы которого отличаются на <tex>\pm 1</tex>. Поступают онлайн запросы вида <tex>(l, r)</tex>, для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \ldots, A[r] </tex>.
 +
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
[[Файл:F-C_B_algo.png|right|thumb|Части, из которых состоит ответ на запрос RMQ]]
 
  
Данный алгоритм основывается на методе решения задачи RMQ с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.
+
Данный алгоритм основывается на методе решения задачи <tex>RMQ</tex> с помощью [[Решение RMQ с помощью разреженной таблицы|разреженной таблицы (sparse table, ST)]] за <tex>\langle O(N \log N),O(1) \rangle</tex>.
 +
 
 +
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <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{\log_2 N}{2}</tex>. Для каждого блока вычислим минимум на нём и определим <tex>b_i</tex> как позицию минимального элемента в <tex>i</tex>-том блоке.
 
  
На новой последовательности <tex>b_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос RMQ<tex>[i:j]</tex>, если <tex>i</tex> и <tex>j</tex> находятся в разных блоках, нам необходимо вычислить следующее:
+
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[l:r]</tex>, если <tex>l</tex> и <tex>r</tex> находятся в разных блоках, нам необходимо вычислить следующее:
# минимум на отрезке от <tex>i</tex> до конца содержащего <tex>i</tex> блока;
+
# минимум на отрезке от <tex>l</tex> до конца блока, содержащего <tex>l</tex>;
# минимум по всем блокам, находящимся между блоками, содержащими <tex>i</tex> и <tex>j</tex>;
+
# минимум по всем блокам, находящимся между блоками, содержащими <tex>l</tex> и <tex>r</tex>;
# минимум от начала блока, содержащего <tex>j</tex>, до <tex>j</tex>.
+
# минимум от начала блока, содержащего <tex>r</tex>, до <tex>r</tex>.
 
Ответом на запрос будет позиция меньшего из эти трёх элементов.
 
Ответом на запрос будет позиция меньшего из эти трёх элементов.
  
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>b_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
+
[[Файл:F-C_B_algo.png|500px|center|Части, из которых состоит ответ на запрос RMQ]]
 +
 
 +
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>B_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
  
 
=== Минимум внутри блока ===
 
=== Минимум внутри блока ===
Строка 23: Строка 27:
 
{{Утверждение
 
{{Утверждение
 
|id=sameblocks
 
|id=sameblocks
|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос RMQ даст один и тот же ответ для обеих последовательностей.
+
|statement=Если две последовательности <tex>x_i</tex> и <tex>y_i</tex> таковы, что все их элементы на соответствующих позициях различаются на одну и ту же константу (т.е. <tex>\forall k: x_k = y_k + C</tex>), то любой запрос <tex>RMQ</tex> даст один и тот же ответ для обеих последовательностей.
 
}}
 
}}
  
Строка 31: Строка 35:
 
|id=kindscount
 
|id=kindscount
 
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.
 
|statement=Существует <tex>O(\sqrt N)</tex> различных типов нормализованных блоков.
|proof=Соседние элементы в блоках отличаются на ±1. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен ±1-вектором длины <tex>(\frac{\log_2 N}{2}) - 1</tex>. Таких векторов <tex>2^{(1/2 \cdot \log_2 N) - 1} = O(\sqrt N)</tex>.
+
|proof=Соседние элементы в блоках отличаются на <tex>\pm 1</tex>. Первый элемент в нормализованном блоке всегда равен нулю. Таким образом, каждый нормализованный блок может быть представлен <tex>\pm 1</tex>-вектором длины <tex> (\frac{1}{2} \log_2 N) - 1</tex>. Таких векторов <tex>2^{(\frac{1}{2} \log_2 N) - 1} = O(\sqrt N)</tex>.
 
}}
 
}}
  
Осталось создать <tex>O(\sqrt N)</tex> таблиц по одной для каждого типа блока. В такую таблицу необходимо занести предподсчитанные ответы на все возможные запросы минимума внутри блока соответствующего типа, коих <tex>(\frac{\log_2 N}{2})^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> времени.
 +
 
 +
 
 +
=== Псевдокод ===
 +
<code>
 +
 
 +
  precalc(A : '''int[]''', N : '''int''')
 +
    block_size = log(N) / 2 <font color=green> // размеры блоков </font>
 +
    K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font>
 +
    <font color=green>// предподсчитаем позиции минимумов в каждом блоке</font>
 +
    cur_block = 0
 +
    j = 0
 +
    '''for''' i = 0 '''to''' K - 1
 +
      B[i] = -1
 +
    '''for''' i = 0 '''to''' N - 1
 +
      '''if''' j <tex>\ge</tex> block_size
 +
        j = 0
 +
        cur_block++
 +
      '''if''' B[cur_block] = -1 '''or''' A[B[cur_block]] > A[i]
 +
        B[cur_block] = i
 +
    <font color=green>// построим Sparse table на массиве B</font>
 +
    '''for''' i = 0 '''to''' K - 1
 +
      ST[i][0] = B[i]
 +
    '''for''' j = 1 '''to''' log(N)
 +
      '''for''' i = 0 '''to''' K - 1
 +
        ind = (1 << (j - 1)) + i
 +
        '''if''' ind <tex>\ge</tex> K
 +
          ST[i][j] = ST[i][j - 1]
 +
        '''else if''' A[ST[i][j - 1]] > A[ST[ind][j - 1]]
 +
          ST[i][j] = ST[ind][j - 1]
 +
        '''else'''
 +
          ST[i][j] = ST[i][j - 1]
 +
    <font color=green>// Посчитаем хеш для каждого блока {{---}} он будет являться типом блока</font>
 +
    cur_block = 0
 +
    j = 0
 +
    '''for''' i = 0 '''to''' K - 1
 +
      hash[i] = 0
 +
    '''for''' i = 0 '''to''' N - 1
 +
      '''if''' j <tex>\ge<tex> block_size
 +
        j = 0
 +
        cur_block++
 +
      '''if''' j > 0 '''and''' (i <tex>\ge</tex> n '''or''' A[i - 1] < A[i])
 +
        hash[cur_block] += (1 << (j - 1))
 +
    <font color=green>// Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках</font>
 +
    '''for''' i = 0 '''to''' K - 1
 +
      '''for''' l = 0 '''to''' block_size - 1
 +
        '''for''' r = 0 '''to''' block_size - 1
 +
          block_min[i][l][r] = -1
 +
    '''for''' i = 0 '''to''' K - 1
 +
      type = hash[i]
 +
      '''if''' block_min[type][0][0] = -1 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font>
 +
        '''for''' l = 0 '''to''' block_size - 1
 +
          block_min[type][l][l] = l
 +
          '''for''' r = l + 1 '''to''' block_size - 1
 +
            block_min[type][l][r] = block_min[type][l][r - 1]
 +
            '''if''' i * block_size + r <tex>\le</tex> N '''and''' A[i * block_size + block_min[type][l][r]] > A[i * block_size + r]
 +
                block_min[type][l][r] = r
 +
 
 +
  '''int''' block_RMQ(block_number : '''int''', l : '''int''', r : '''int''')
 +
    '''return''' block_min[hash[block_number]][l][r] + block_number * block_size
 +
 
 +
  '''int''' RMQ(l : '''int''', r : '''int''')
 +
    bl = l / block_size
 +
    br = r / block_size
 +
    '''if''' bl = br <font color=green>// если оба индекса внутри одного блока</font>
 +
      '''return''' A[block_RMQ(bl, l % block_size, r % block_size)]
 +
    '''if''' bl + 1 < br <font color=green>// найдем минимум на блоках между крайними, если таковые есть</font>
 +
      power = log(br - bl + 1)
 +
      ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
 +
    ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] <font color=green>// найдем минимум на отрезке от l до конца блока, содержащего l</font>
 +
    ansr = A[block_RMQ(bl, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font> 
 +
    '''return''' min(ansb, min(ansl, ansr))
 +
 
 +
   
 +
 
 +
</code>
  
 
=== Результат ===
 
=== Результат ===
Строка 44: Строка 123:
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи LCA к задаче RMQ]]
  
== Источники ==
+
==Источники информации==
* ''Bender, M.A., Farach-Colton, M.'' — '''The LCA Problem Revisited'''. LATIN (2000), с. 88-94
+
* Bender, M.A., Farach-Colton, M. {{---}} The LCA Problem Revisited. LATIN (2000), с. 88-94
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о наименьшем общем предке]]
 
[[Категория: Задача о наименьшем общем предке]]

Версия 22:11, 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]-ом блоке.


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

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

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

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

Второй элемент мы уже умеем находить за [math]O(1)[/math] с помощью [math]B_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] времени.


Псевдокод

 precalc(A : int[], N : int) 
   block_size = log(N) / 2  // размеры блоков 
   K = [math]\lceil[/math]N / block_size[math]\rceil[/math]  // количество блоков  
   // предподсчитаем позиции минимумов в каждом блоке
   cur_block = 0
   j = 0 
   for i = 0 to K - 1 
     B[i] = -1 
   for i = 0 to N - 1
     if j [math]\ge[/math] block_size 
       j = 0
       cur_block++ 
     if B[cur_block] = -1 or A[B[cur_block]] > A[i]
       B[cur_block] = i
   // построим Sparse table на массиве B
   for i = 0 to K - 1
     ST[i][0] = B[i]
   for j = 1 to log(N)
     for i = 0 to K - 1
       ind = (1 << (j - 1)) + i
       if ind [math]\ge[/math] K
         ST[i][j] = ST[i][j - 1]
       else if A[ST[i][j - 1]] > A[ST[ind][j - 1]]
         ST[i][j] = ST[ind][j - 1] 
       else
         ST[i][j] = ST[i][j - 1]
   // Посчитаем хеш для каждого блока — он будет являться типом блока
   cur_block = 0
   j = 0
   for i = 0 to K - 1 
     hash[i] = 0 
   for i = 0 to N - 1
     if j [math]\ge\lt tex\gt  block_size 
        j = 0
        cur_block++ 
      '''if''' j \gt  0 '''and''' (i \lt tex\gt \ge[/math] n or A[i - 1] < A[i])
       hash[cur_block] += (1 << (j - 1)) 
   // Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках
   for i = 0 to K - 1
     for l = 0 to block_size - 1
       for r = 0 to block_size - 1
         block_min[i][l][r] = -1 
   for i = 0 to K - 1
     type = hash[i]
     if block_min[type][0][0] = -1 // если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков
       for l = 0 to block_size - 1
         block_min[type][l][l] = l
         for r = l + 1 to block_size - 1
           block_min[type][l][r] = block_min[type][l][r - 1]
           if i * block_size + r [math]\le[/math] N and A[i * block_size + block_min[type][l][r]] > A[i * block_size + r]
               block_min[type][l][r] = r
 int block_RMQ(block_number : int, l : int, r : int)
   return block_min[hash[block_number]][l][r] + block_number * block_size
 int RMQ(l : int, r : int)
   bl = l / block_size
   br = r / block_size
   if bl = br // если оба индекса внутри одного блока
     return A[block_RMQ(bl, l % block_size, r % block_size)]
   if bl + 1 < br // найдем минимум на блоках между крайними, если таковые есть
     power = log(br - bl + 1)
     ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
   ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] // найдем минимум на отрезке от l до конца блока, содержащего l
   ansr = A[block_RMQ(bl, 0, r % block_size)] // найдем минимум от начала блока, содержащего r, до r    
   return min(ansb, min(ansl, ansr))


Результат

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

См. также

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

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