Изменения

Перейти к: навигация, поиск
Нет описания правки
[[Файл:Down-up2.png‎|right|255px|thumb|Реализация запроса снизу вверх]]==Алгоритм==
==Алгоритм==Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> \circ </tex> b.
Реализация запроса снизу вверх [[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в дереве отрезков 3 этапа: 1. Если элемент, попавший на левую границу, являетсяправым сыном, то запишем в отличие результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей(является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от [[Реализация запроса вклада ненужного нам поддерева. 2. Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в дереве отрезков сверху| реализации запроса сверху вниз]]искомый или нет. Повторяем этап 1), итеративным методомпока границы не пересекутся. 3. Будем рассматривать абстрактную операциюЕсли после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, обладающую свойством ассоциативностии надо пересчитать результат.
[[Дерево отрезковФайл:ДО_снизу_вверх. Построениеpng‎|Построим дерево отрезков800px|Реализация запроса снизу вверх]] и установим границы отрезка на соответствующие листья. Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. Аналогично действуем с элементом попавшим на правую границу (является ли этот элемент левым сыном). Затем устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Продолжаем до тех пор, пока границы не пересекутся. Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат, иначе {{---}} ничего делать не надо.
==Псевдокод==
Пусть ассоциативная операция, над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right]. При этом значения передающиеся в функцию left и right должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья).
query(left, right)
result = neutral; // Присваиваем результату значение нейтрального элемента (например для поиска суммы надо присвоить значение 0) '''while''' left < right // Выполняем цикл до тех пор, пока левая и правая граница не пересекутся '''if''' left mod 2 == 0 // Проверяем, является ли левая граница правым сыном (индексация с 0) result = result <tex> \circ </tex> data[left]; // Если является, то пересчитаем результат и перенесем левую границу
left = left div 2;
// Если не является, то установим границу на родительский элемент текущей границы '''if''' right mod 2 == 1 // Аналогично проделываем операции с правой границей
result = result <tex> \circ </tex> data[right];
right = (right - 2) div 2;
'''if''' left == right // После окончания цикла проверяем совпали ли границы result = result <tex> \circ </tex> data[left]; // Если надо пересчитываем результат
'''return''' result;
94
правки

Навигация