В 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.
А в коде и в статье используется как раз медленный вариант.