Q: Gcd and update query i have a sequence of numbers A[0] to A[n-1].
there can be 2 possible queries.
query 1 : gcd i j : Calculate gcd of all nos. A[k] such that i<=k<=j.
query 2 : update i j : change A[i] to j
eg.
gcd 2 4
gcd 1 5
update 2 3
gcd 2 4
update 4 1
gcd 3 6

What is the fastest algorithm to do this ?

A: Good question,
the first idea that comes into mind is to use segment trees. If you are not familiar with segment trees here is very useful tutorial for that. On each node we can keep gcd of numbers in segment which is covered by that node. So we will need to consider logn number of nodes for each update query, and for second query we can just return value which is kept in the root node. For each node we will need to count gcd of its two children values, so update query needs O((logn)^2) time and the second query will need O(1) time.
Here is the link for segment trees:
https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees
