For sum, XOR, or other non-idempotent operations, decompose the range into non-overlapping power-of-2 ranges:
function querySum(l, r):
result = 0
length = r - l + 1
for j = LOG[length] down to 0:
if (1 << j) <= length:
result += st[l][j]
l += (1 << j)
length -= (1 << j)
return result
The operation takes time. Same as segment tree. So for sum queries, Sparse Table offers no advantage; use BIT or segment tree instead.
Sparse Table shines for idempotent operations with many queries.