Segment Tree Range GCD Query

Problem

Support point updates and range-GCD queries with a segment tree. nums is the initial array. queries contains ["update", i, val] (set nums[i] = val) or ["gcd", l, r] (GCD of nums[l..r] inclusive). Combine nodes with math.gcd and let an out-of-range side contribute 0, the identity for GCD. Return the query results in order.

Hint

GCD is associative and gcd(0, x) = x, so 0 works as the identity for empty ranges.

Test cases

case 1

in: [[12,18,24,30],[["gcd",0,3],["update",1,7],["gcd",0,3],["gcd",1,2]]]

expected: [6,1,1]

case 2

in: [[5,5,5,5],[["gcd",0,0],["update",2,9],["gcd",0,3],["gcd",2,2]]]

expected: [5,1,9]

case 3

in: [[0],[["gcd",0,0],["update",0,6],["gcd",0,0]]]

expected: [0,6]

Starter codePython

def segment_tree_gcd(nums, queries):
    # Your code here
    pass

3 test cases · run your code against them in the editor