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