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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/the-overlap-trick

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

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

$ curl repovive.com/roadmaps/data-structures/sparse-tables/the-overlap-trick

Repovive

The Overlap Trick - Sparse Tables | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

The Overlap Trick

Idempotent operations

To query range $[l, r]$ :

$1.$ Find the largest power of 2 that fits: $k = \lfloor \log_2(r - l + 1) \rfloor$

$2.$ Take $\min$ of two overlapping ranges of length $2^k$ :

One starting at $l$ : $\text{st}[l][k]$
One ending at $r$ : $\text{st}[r - 2^k + 1][k]$

def query(l, r):
    length = r - l + 1
    k = int(log2(length))
    return min(st[l][k], st[r - (1 << k) + 1][k])

These two ranges cover $[l, r]$ completely, possibly overlapping in the middle. Since $\min$ is idempotent, overlapping is fine.

Time: $O(1)$ per query (with precomputed $\log$ values).