<tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
|proof=
Мы знаем что:Положим <tex>w = LCA(A[i], A[j])</tex>. * Любая вершина дерева всегда имеет меньшее или равное значениеЗаметим, чем её дети. Тогда любой предок что <tex>A[i]</tex> или и <tex>A[j]</tex> меньше или равен им самим.* не принадлежат одновременно либо правому, либо левому поддереву <tex>w</tex>, потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>w</tex>, и также являлся предком как <tex>LCA(A[i], </tex> так и <tex>A[j])</tex> ближайший к корню и по п, что противоречит определению <tex>LCA</tex>.1 имеет наименьшее значение в своем поддереве. По построениюИз этого замечанию следует, это поддерево содержит в частности подмассив что <tex>w</tex> лежит между <tex>A[i..j], </tex> и <tex>LCA(A[ij]</tex> и, следовательно, принадлежит отрезку <tex>A[i..j])</tex> находится между . По построению мы также знаем, что:# Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.# Поддерево с корнем в <tex>A[i]w</tex> и содержит в себе подмассив <tex>A[i..j]</tex>. То есть Суммируя, получаем, что <tex>w</tex> имеет минимальное значение на отрезке, покрывающем <tex>LCA(A[i..j]</tex>, и принадлежит отрезку <tex>A[i..j])</tex> является , отсюда <tex>RMQ(i, j).= w</tex>.
}}
== Построение дерева за линейное время ==
Пусть дан массив <tex>A[1..N]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение <tex>A[i]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину <tex>x</tex>, для которой <tex>x < A[i]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а <tex>A[i]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>O(n)</tex>.
