Блог пользователя yahooo

Минимум на отрезке за O(1)
Автор yahooo, 13 лет назад, По-русски

Лишь один вопрос. Почему тут написано решение с декартовым деревом, а тут в конце статьи по-моему тот же алгоритм Фарах-Колтона и Бендера, который, как утверждает e-maxx, работает лишь на массиве, где соседние элементы отличаются на ровно на 1?

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Алгоритма Фарах-Колтона и Бендера, если верить e-maxx, решает задачу LCA, сводя ее к +-1 RMQ. Таким образом, он работает на дереве, а не на массиве. Отсюда вопрос:
"Почему огурцы ложкой банка майонеза?"
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится
    Собственно алгоритм Фарах-Колтона и Бендера как раз и представляет собой решение такой задачи RMQ.

    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Там такой план:
1. Придумать быстрое +-1 RMQ.
2. Придумать быстрое LCA.
3. Построить декартово дерево определенного вида для заданной последовательности. На нем LCA краев будет в точности равно RMQ отрезка.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, я понял, но просто на википедии решение этой задачи вроде как без него и вроде как правильное, или нет?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Напишу проще.

Проблема: RMQ за O(1)

Решение1: с декартовым деревом отсюда

Решение2: со sparse table отсюда

Вопрос: Какое правильное? На википедии вроде написан вариант для +-1 или нет?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    С декартовым деревом O(n) препроцессинга. Со sparse table O(n*log(n)). А так оба правильные.
    → Ответить
13 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Тогда запрос RMQ(l,r) эквивалентен запросу LCA(l',r'), где l' - вершина, соответствующая элементу A[l]...
То есть l' - ключ той вершины, у которой приоритет равен A[l]?

UPD. Уже понял.

UPD2. Тогда возникает другая проблема, а если у нас есть одинаковые элементы во входном массиве?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А в чем разница, если есть одинаковые? Ключи-то разные у всех.
    → Ответить