НОД чисел на отрезке

#алгоритм

Как можно реализовать дерево отрезков для ответа на запрос НОД на отрезке так, чтобы
время работы каждого запроса составляло O(log n + log C), где C - максимальное значение?
    

Ответы

Ответ 1

Доработанный алгоритм:


Массив элементов дополняется до степени двойки, фиктивные элементы заполняем нулями.
Дополняем функцию НОД правилом НОД(a,0)=a.  
В узлах храним не НОД, а код. Для вычисления кодов узлов сначала на проходе снизу
вверх записываем НОД в родительские узлы, потом на проходе сверху вниз на место НОД
записываем коды дочерних узлов, вычисляемые как отношение НОД узла (или значения элемента)
к произведению родительских кодов.
При такой структуре истинное значение НОД каждого узла (в том числе - значение "нижнего"
элемента) будет равно произведению кодов самого узла и всех родительских узлов. Код
корневого узла равен НОД всех элементов отрезка.
Отработка запроса НОД подотрезка ведётся путём корректировки кодов пограничных узлов
снизу вверх.
Узел считается пограничным, если среди его потомков содержатся как внешние, так и
внутренние узлы. При отработке запроса НОД код пограничного узла умножается на код
пограничного (либо внутреннего) дочернего узла.
Узел считается крайним, если оба его дочерних узла пограничные. Код крайнего узла
вычисляется как НОД от кодов дочерних узлов.
Корректировка кодов завершается при достижении крайнего либо корневого узла. НОД
подотрезка равен коду корневого узла либо произведению кода крайнего узла
на коды его родительских узлов.


Схему вычислений иллюстрирует рисунок



Обработка каждого подотрезка ведётся только вдоль его границ. Это позволяет говорить
о требуемой эффективности алгоритма.


Ответ 2

Собственно сам НОД в узлах и хранить.

При подъёме использовать сужающий метод, т. е. для левого края в случае левой вершины
поднимаемся, в случае правой считаем функцию для неё и предка следующей; для правого
края аналогично симметрично.