Often you need not the minimum value, but its position.
Store pairs in the sparse table. The merge takes the pair with smaller value (or smaller index to break ties).
function build():
for i = 0 to n - 1:
st[i][0] = (arr[i], i)
for j = 1 to K - 1:
for i = 0 to n - (1 << j):
left = st[i][j-1]
right = st[i + (1 << (j-1))][j-1]
if left[0] <= right[0]:
st[i][j] = left
else:
st[i][j] = right
function query(l, r):
k = LOG[r - l + 1]
left = st[l][k]
right = st[r - (1 << k) + 1][k]
if left[0] <= right[0]:
return left
else:
return right
Returns both the minimum value and its index in .