Изменения

В-третьих, для каждого запроса проверка условия и определение результата, опять же, для всех разумных <tex>n</tex> выполняется за <tex>O (1)</tex>. Итоговая асимптотика получается <tex>O (n + m)</tex>, но при достаточно больших <tex>m</tex> ответ за <tex>O (1)</tex> на один запрос.

* [http://e-maxx.ru/algo/lca_linear_offline e-maxx.ru - алгоритмы]

* [http://habrahabr.ru/post/104772 habrahabr - Система непересекающихся множеств и её применения]