1 Отредактировано matklad (2012-03-30 19:00:46)

Тема: lca за O(1)

В http://www.e-maxx.ru/algo/lca_linear написанно:

мы должны предпосчитать значения sz для всех возможных длин, которых есть O (log N) штук

А разве этих длин не O(N) штук?

update:
сейчас сдал задачу про lca с помощью Sparse Table и заметил интересный эффект:

если в T первый индекс это l, а второй i, то препроцесинг работает две секунды, запросы семь секунд и задача не проходит по TL.

А если индексы поменять местами, то препроцессинг - одна секунда, запросы - четыре секунды и задача проходит.

Это логично, так как при пересчёте T[l,i] = min (T[l,i-1], T[l+2^(i-1),i-1]) и при ответе на запрос ans = min (T[l,sz], T[r-2^sz+1,sz]) используются два элемента с одинаковыми i.

А в коде и в статье используется как раз медленный вариант.

2

Re: lca за O(1)

matklad пишет:

В http://www.e-maxx.ru/algo/lca_linear написал:

мы должны предпосчитать значения sz для всех возможных длин, которых есть O (log N) штук

А разве этих длин не O(N) штук?

да, была опечатка, спасибо, исправил.

matklad пишет:

В http://www.e-maxx.ru/algo/lca_linear написал:
update:
сейчас сдал задачу про lca с помощью Sparse Table и заметил интересный эффект:

если в T первый индекс это l, а второй i, то препроцесинг работает две секунды, запросы семь секунд и задача не проходит по TL.

А если индексы поменять местами, то препроцессинг - одна секунда, запросы - четыре секунды и задача проходит.

Это логично, так как при пересчёте T[l,i] = min (T[l,i-1], T[l+2^(i-1),i-1]) и при ответе на запрос ans = min (T[l,sz], T[r-2^sz+1,sz]) используются два элемента с одинаковыми i.

А в коде и в статье используется как раз медленный вариант.

Да, действительно почти всегда быстрее оказывается ставить вершину вторым индексом, но 4 года назад я этого не знал smile
Код пока не рискую исправлять, чтобы не посадить баги, исправлю при следующем переписывании статьи.