Range GCD Solution

class SparseTableGCD:
    function init(arr):
        this.n = arr.length
        this.LOG = array of size (this.n + 1), filled with 0
        for i = 2 to this.n:
            this.LOG[i] = this.LOG[i / 2] + 1

        K = this.LOG[this.n] + 1
        this.st = 2D array of size this.n x K, filled with 0

        for i = 0 to this.n - 1:
            this.st[i][0] = arr[i]

        for j = 1 to K - 1:
            for i = 0 to this.n - (1 << j):
                this.st[i][j] = gcd(
                    this.st[i][j-1],
                    this.st[i + (1 << (j-1))][j-1]
                )

    function query(l, r):
        k = this.LOG[r - l + 1]
        return gcd(this.st[l][k], this.st[r - (1 << k) + 1][k])

The only change from RMQ: replace $\min$ with $\gcd$.