Реализация запроса в дереве отрезков снизу — различия между версиями
Gemin (обсуждение | вклад) (→Псевдокод) |
Lirik (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | [[Файл:Down-up1.png|right|255px|thumb|Реализация запроса снизу вверх]] | |
| − | Реализация запроса снизу вверх | + | |
==Алгоритм== | ==Алгоритм== | ||
| − | + | ||
| − | Будем рассматривать дерево отрезков с операцией нахождения минимального значения | + | Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения(RMQ). |
| − | Установим границы отрезка на соответствующие листья. Если элемент попавший на левую границу является правым сыном, то | + | |
| + | Установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то вычисляем результат как минимум между предыдущем результатом и значением этого элемента. Левая граница перемещается на один элемент вправо. Иначе левую границу не трогаем. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Продолжаем до тех пор, пока границы не пересекутся. | ||
==Псевдокод== | ==Псевдокод== | ||
| − | |||
| − | + | Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1. | |
| − | + | ||
| − | while left < right | + | //Функция нахождения минимального элемента на отрезке <tex>[left, right]</tex> |
| − | if | + | Min(left, right) |
| − | + | result = +inf; //Присваиваем результату максимально возможное значение | |
| − | left = | + | while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут |
| + | if ((left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном | ||
| + | result = min(result, left.data); // Если является то пересчитаем результат и перенесем левую границу | ||
| + | left = (left + 1) / 2; | ||
else | else | ||
| − | left = | + | left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы |
| − | if | + | if ((right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей |
| − | + | result = min(result, right.data); | |
| − | right = | + | right = (right - 1) / 2; |
else | else | ||
| − | right = | + | right = (right) / 2; |
| − | + | if (left == right) // После окончания цикла проверяем совпали ли границы | |
| − | + | result = min(result, left.data); // Если надо пересчитываем результат | |
| − | + | return result; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | return | ||
==Ссылки== | ==Ссылки== | ||
Версия 14:20, 24 мая 2012
Алгоритм
Реализация запроса снизу вверх в дереве отрезков является, в отличие от реализации сверху вниз, итеративным методом. Будем рассматривать дерево отрезков с операцией нахождения минимального значения(RMQ).
Установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то вычисляем результат как минимум между предыдущем результатом и значением этого элемента. Левая граница перемещается на один элемент вправо. Иначе левую границу не трогаем. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Продолжаем до тех пор, пока границы не пересекутся.
Псевдокод
Пусть дерево отрезков реализовано на массиве с индексацией элементов с 1.
//Функция нахождения минимального элемента на отрезке
Min(left, right)
result = +inf; //Присваиваем результату максимально возможное значение
while (left < right) //Выполняем цикл до тех пор пока левая и правая граница не совпадут
if ((left) / 2) * 2 == left // Проверяем является ли левая граница правым сыном
result = min(result, left.data); // Если является то пересчитаем результат и перенесем левую границу
left = (left + 1) / 2;
else
left = (left) / 2; // Если не является, то установим границу на родительский элемент текущей границы
if ((right) / 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
result = min(result, right.data);
right = (right - 1) / 2;
else
right = (right) / 2;
if (left == right) // После окончания цикла проверяем совпали ли границы
result = min(result, left.data); // Если надо пересчитываем результат
return result;
