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