GCD между диапазонами

Question

Я дал массив размера N. У меня есть Q-запросы. Мне нужно рассчитать gcd между L и R, где LR, где 1 ≤ L ≤ R ≤ N.

Как правильно рассчитать его как грубую силу подход не удастся.

Answer 1

GCD является аддитивным и коммутативным. Это означает, что дерево сегментов может решить эту проблему с использованием log (N) времени для каждого запроса GCD диапазона.

Wikipedia has a nice article about segment trees

Answer 2

Сегмент дерево может быть использовано для предварительной обработки и запроса в умеренное время. С деревом сегментов время предварительной обработки - O (n), а время для запроса GCD - O (Logn). Требуемое дополнительное пространство - это O (n) для хранения дерева сегментов.

Представление сегментов деревьев

• листьев узлы являются элементы входного массива.
• Каждый внутренний узел представляет собой GCD всех листов под ним.

Массив представление дерева используется для представления сегментов деревьев т.е. для каждого узла с индексом I,

• Левый ребенок имеет индекс 2 * я + 1
• Право ребенка на 2 * я +2, а родительский элемент находится на этаже ((i-1)/2).

Осуществлению можно найти здесь http://www.geeksforgeeks.org/gcds-of-a-given-index-ranges-in-an-array/