Non-Idempotent Queries

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 $O(\log n)$ 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.