94
правки
Изменения
Нет описания правки
==Псевдокод==
Пусть ассоциативная операция выполняется функцией operation(arg1, arg2)над которой построено дерево отрезков, обозначается a <tex> \circ </tex> b, а результат считаем на отрезке [left, right].
while left < right //Выполняем цикл до тех пор, пока левая и правая граница не пересекутся
if (left div 2) * 2 == left // Проверяем, является ли левая граница правым сыном (индексация с 0)
result = operation(result, <tex> \circ </tex> data[left]); // Если является, то пересчитаем результат и перенесем левую границу
left = (left + 1) div 2;
else
left = left div 2; // Если не является, то установим границу на родительский элемент текущей границы
if (right div 2) * 2 + 1 == right // Аналогично проделываем операции с правой границей
result = operation(result, <tex> \circ </tex> data[right]);
right = (right - 1) div 2;
else
right = right div 2;
if left == right // После окончания цикла проверяем совпали ли границы
result = operation(result, <tex> \circ </tex> data[left]); // Если надо пересчитываем результат
return result;
