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