#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sparse-tables/non-idempotent-queries

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sparse-tables/non-idempotent-queries

Repovive

Non-Idempotent Queries - Sparse Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Non-Idempotent Queries

O(log n) fallback

For sum, XOR, or other non-idempotent operations, decompose the range into non-overlapping power-of-2 ranges:

def querySum(l, r):
    result = 0
    length = r - l + 1
    for j in range(LOG[length], -1, -1):
        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.