У меня есть последовательность чисел A [0] - A [n-1].Gcd и запрос на обновление
может быть 2 возможных запроса.
query 1: gcd i j: Рассчитать gcd всех nos. A [k] такой, что i < = k < = j.
запрос 2: обновление I J: изменение A [я] для J
например.
gcd 2 4
gcd 1 5
update 2 3
gcd 2 4
update 4 1
gcd 3 6
Что является самым быстрым алгоритмом для этого?
Хороший вопрос,
первая мысль, которая приходит на ум, является использование сегментных деревьев. Если вы не знакомы с деревьями сегментов, здесь очень полезный учебник для этого. На каждом узле мы можем сохранить gcd чисел в сегменте, который покрывается этим узлом. Поэтому нам нужно будет учитывать количество узлов для каждого запроса на обновление, а для второго запроса мы можем просто вернуть значение, которое хранится в корневом узле. Для каждого узла нам нужно будет подсчитать gcd его двух дочерних значений, поэтому для запроса обновления требуется время O ((logn)^2), а для второго запроса потребуется время O (1).
Вот ссылка для сегмента деревьев: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees
Я знаю деревья сегментов. Меня заинтересовало то, что если для этого существует более быстрая техника: P –
Быстрее, чем O (logn), вы имеете в виду O (1)? Может быть, для квантовых компьютеров – Mamuka
делать то, что именно? найти gcd? – Lrrr
есть два типа запросов. для каждого запроса мне нужно дать соответствующий ответ. @AliAmiri –
Для обмена есть очевидный ответ O (1), temp = a [i], a [i] = a [j], a [j] = temp. но я сейчас думаю о самом быстром способе для GCD. – Lrrr