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 with .