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