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