Изменения
Нет описания правки
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит как минимум в частности подмассив <tex>A[i..j]., </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и <tex>A[j]</tex> . То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построения за <tex>O(n)</tex>.
