Изменения

Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать [[декартово дерево по неявному ключу]]. Тогда минимум на отрезке от <tex> i </tex> до <tex> j </tex> массива <tex> A </tex> будет равен наименьшему общему предку <tex>i</tex>-того и <tex>j</tex>-того элементов из декартова дерева , построенного на массиве <tex> A </tex>.

Заметим, что <tex>A[i]</tex> и <tex>A[j]</tex> не принадлежат одновременно либо правому, либо левому поддереву <tex>w</tex>, потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>w</tex>, и также являлся предком как <tex>A[i]</tex> , так и <tex>A[j]</tex>, что противоречит определению <tex>LCA</tex>. Из этого замечанию замечания следует, что <tex>w</tex> лежит между <tex>A[i]</tex> и <tex>A[j]</tex> и, следовательно, принадлежит отрезку <tex>A[i..j]</tex>.