Key observation. Fix a left end and extend the group to the right. The values \gcd(a_i, \ldots, a_j) form a divisor chain, and each time the value changes it becomes a proper divisor of the previous one, so it at least halves. Since a_i \le 10^9 < 2^{30}, there are at most distinct values. So the prefix gcds of any segment split into O(\log A) blocks of consecutive prefixes with equal gcd, and the same holds for suffixes.
Segment tree. For each node store: , the number of convenient groups inside it; , the gcd of the whole node; , the list of distinct prefix gcds in order of growing prefix, each with the number of prefixes having it; and , the same for suffixes. A leaf with value has \mathrm{cnt} = [x > 1] and \mathrm{pre} = \mathrm{suf} = ((x, 1)).
To merge a left child with a right child : \mathrm{tot} = \gcd(L.\mathrm{tot}, R.\mathrm{tot}); is followed by the blocks (\gcd(L.\mathrm{tot}, g), c) for in , with equal neighbours joined, and symmetrically. Finally, \mathrm{cnt} = L.\mathrm{cnt} + R.\mathrm{cnt} + \mathrm{cross}, where counts the convenient groups that cross the middle, i.e. pairs (suffix of , prefix of ) with \gcd(s, g) > 1, weighted by the multiplicities.
Counting crossing pairs. If \gcd(s, g) > 1 for a suffix gcd and a prefix gcd , then the same holds for every shorter suffix and every shorter prefix, since their gcds are multiples of and . So when the suffix grows, the set of prefixes that pair well with it is a prefix of that can only shrink. Go through in order of growing length and move a pointer backwards through while the current pair has gcd , keeping the total multiplicity of the remaining prefix blocks. This takes O(\log A) gcd computations per merge.
Operations. An update changes a leaf and re-merges its O(\log n) ancestors. A query [l, r] folds the O(\log n) canonical nodes from left to right with the same merge; the accumulator needs only , and . The answer can reach n(n+1)/2 \approx 4.5 \cdot 10^{10}, so it needs 64-bit integers.
The complexity is O((n + q) \log n \log A) gcd computations, where A = 10^9. Memory is , since a node of length has lists of length at most \min(k, 31).