Sparse Table

Sparse Table | Algoryva

Intuition

Two overlapping mileposts

Suppose you want the lowest point on any stretch of a long road, and you have already written down the lowest point of every stretch that is 1, 2, 4, 8, … km long, starting at every kilometre. For a 6 km stretch, take the lowest point of a 4 km stretch at its start, and the lowest point of a 4 km stretch at its end. Together they cover the whole 6 km, with a 2 km overlap in the middle.

The overlap does not matter for “lowest point”: counting the same stretch twice cannot change a minimum. That small observation turns each query into two lookups.

First, the naive way

Precompute every possible answer

The most direct way to make queries instant is to store the answer for every range (l, r) in advance. Each query becomes one dictionary lookup.

But there are n(n + 1)/2 ranges: 36 for 8 values, 125,250 for 500, and about 5 × 10⁹ for n = 10⁵. Time and memory to build the table are both O(n²).

python

def all_answers(a):
    n = len(a)
    ans = {}
    for l in range(n):
        cur = a[l]
        for r in range(l, n):
            cur = min(cur, a[r])
            ans[(l, r)] = cur
    return ans

a = [5, 2, 6, 1, 7, 3, 8, 4]
table = all_answers(a)
print(table[(1, 6)])   # 1
print(len(table))   # 36
print(len(all_answers(list(range(500)))))   # 125250

Cost: O(n²) time and memory to build: impossible for n = 10⁵.

The observation

Only powers of two are needed, because overlap is harmless

Store answers only for blocks whose length is a power of two (1, 2, 4, 8, …). There are about n blocks per length and log₂ n lengths, so n log n answers in total instead of n².

Any range is covered by two blocks of the same power-of-two length: the largest power 2^k that fits inside the range, placed at its left end and at its right end. For minimum, maximum, gcd, and, or, the overlap is harmless, because min(x, x) = x: such operations are called idempotent. A sum is *not* idempotent (overlapped values would be counted twice), so a sparse table cannot answer overlapping sums in O(1).

The concept

How the table is organised

Row k of the table holds blocks of length 2^k.

t[k][i] = the answer (min, max, gcd, …) for positions i to i + 2^k − 1.
Row 0 is the array itself (blocks of length 1).
Row k is built from row k − 1: a block of length 2^k is two adjacent blocks of length 2^(k−1), so t[k][i] = op(t[k−1][i], t[k−1][i + 2^(k−1)]).
Row k has n − 2^k + 1 entries (blocks that would run past the end are not stored). There are about log₂ n + 1 rows.
Query [l, r] (inclusive): let len = r − l + 1 and k = floor(log₂ len) (in Python: len.bit_length() − 1). The answer is op(t[k][l], t[k][r − 2^k + 1]).
Idempotent operations only for the O(1) query: min, max, gcd, bitwise and, bitwise or.
Static data only: if a value changes, every block containing it changes, so use a segment tree instead.

See it move

Building the table and answering two queries

The top row is the array. Watch the three rows below it fill in: each cell combines two cells of the row above, and the highlighted values show the block it covers. At the end two queries are answered: each picks the largest power-of-two block that fits and uses two overlapping copies (blue and red). The overlap cells are drawn with the blue colour.

Worked by hand

The table for [5, 2, 6, 1, 7, 3, 8, 4], by hand

Minimum over blocks of length 1, 2, 4 and 8 starting at each position:

k (block length)	table row	number of entries
0 (length 1)	5 2 6 1 7 3 8 4	8
1 (length 2)	2 2 1 1 3 3 4	7
2 (length 4)	1 1 1 1 3	5
3 (length 8)	1	1

1
Query positions 1 to 6
Length 6, so k = 2 (4 ≤ 6 < 8). Blocks: t[2][1] covers 1 to 4 and t[2][3] covers 3 to 6 (since 6 − 4 + 1 = 3). min(1, 1) = 1. Positions 3 and 4 are counted twice, which does not matter.
2
Query positions 5 to 7
Length 3, so k = 1. Blocks t[1][5] (positions 5 to 6, value 3) and t[1][6] (positions 6 to 7, value 4). min(3, 4) = 3.

Implementation

A sparse table class

Pass any idempotent operation: min, max or math.gcd.

Plan in plain steps

pseudocode

t[0] = the array
for k = 1 while 2^k <= n: t[k][i] = op(t[k−1][i], t[k−1][i + 2^(k−1)])
query(l, r): k = floor(log2(r − l + 1)); return op(t[k][l], t[k][r − 2^k + 1])

python

Implementation

Check it against brute force

Index arithmetic with r − 2^k + 1 is easy to get off by one. The snippet below tests both a min table and a max table on 300 random arrays of different sizes, including sizes that are not powers of two.

python

from math import gcd

class SparseTable:
    def __init__(self, a, op=min):
        self.op = op
        n = len(a)
        self.t = [list(a)]                       # t[k][i] = op over a[i .. i + 2^k - 1]
        k = 1
        while (1 << k) <= n:
            prev = self.t[k - 1]
            half = 1 << (k - 1)
            self.t.append([op(prev[i], prev[i + half]) for i in (n - ( << k) + )])
            k += 

     (self, l, r):                       
        k = (r - l + ).() -          
         self.(self.t[k][l], self.t[k][r - ( << k) + ])

 random
random.()
ok = 
 _  ():
    n = random.(, )
    a = [random.(-, )  _  (n)]
    lo, hi = (a, min), (a, max)
     _  ():
        l = random.(n)
        r = random.(l, n - )
        ok = ok  lo.(l, r) == (a[l:r + ])  hi.(l, r) == (a[l:r + ])
(ok)

Implementation

Why sums are different

For a sum, overlapping blocks would count the shared values twice. You can still use the same table by splitting the range into disjoint blocks, one for each bit of its length, which takes O(log n) per query, but then a prefix-sum array (O(1)) or a Fenwick tree (with updates) is simply better.

python

def build_sum_table(a):
    n = len(a)
    t = [list(a)]
    k = 1
    while (1 << k) <= n:
        prev, half = t[k - 1], 1 << (k - 1)
        t.append([prev[i] + prev[i + half] for i in range(n - (1 << k) + 1)])
        k += 1
    return t

def range_sum(t, l, r):                        # disjoint blocks: O(log n) because sum is not idempotent
    total = 0
    length = r - l + 1
    k = length.() - 
     length > :
         length >> k & :
            total += t[k][l]
            l +=  << k
        k -= 
        length &= ( << (k + )) - 
     total

a = [, , , , , , , ]
t = (a)
((t, , ))   
((t, , ), (t, , ))   
((a[:]))   
((, ),  + )

Complexity

Costs and comparison with the other tools

Choosing a tool. Static data: sums → prefix sums (O(1)); min, max, gcd → sparse table (O(1) query, O(n log n) memory). Changing data: sums or xor → Fenwick tree; min, max, range updates, or searching → segment tree. For n = 10⁵ a sparse table holds about 1.7 million cells: fine in C++, tight but workable in Python.

Build

time O(n log n)space O(n log n)

About log₂ n rows, each with up to n entries, each computed in O(1) from the row above.

Query (min, max, gcd)

time O(1)space O(1)

Two table lookups and one op, whatever the range length.

Query (sum, using disjoint blocks)

time O(log n)space O(1)

One block per set bit of the length.

Update one value

time O(n) to rebuildspace -

Every block containing the value changes. Use a segment tree for changing data.

Precompute every answer (naive)

time O(n²)space O(n²)

One entry for each of the n(n + 1)/2 ranges.

Edge cases

Range of length 1k = 0, both lookups are the same cell, and the answer is the value itself.
Range equal to a power of twoBoth blocks coincide (r − 2^k + 1 = l): the answer is a single stored cell.
n = 1Only row 0 exists. Queries can only be (0, 0).
Using it for sumsOverlap double-counts. Use prefix sums, or decompose into disjoint blocks.
Data changesThe table becomes stale. Rebuild (O(n log n)) or use a segment tree.
Inclusive versus half-openThis class takes inclusive [l, r]. If your input is half-open, subtract 1 from r.
MemoryFor n = 10⁶ the table has about 2 × 10⁷ cells. Check the memory limit before choosing it.

Common mistakes

Mistakes to avoid

Using a sparse table for range sums or counts in O(1).
Overlapping blocks would count shared elements twice. Only idempotent operations work.
Computing k with floating-point log2 and rounding wrongly.
Use (length).bit_length() − 1, or a precomputed log array.
Second block starting at r − 2^k instead of r − 2^k + 1.
The block must *end* at r, so it starts at r − 2^k + 1. The brute-force check above catches this.
Using it when values change.
Updates need a segment tree.
Building rows with the wrong length.
Row k has n − 2^k + 1 entries; building more indexes past the array.

Recognize it in a contest

How to spot a sparse-table problem

Reach for it when the problem says or implies

Many range queries for the minimum, maximum or gcd, and the array is never updated.
Queries are online (you must answer each as it comes) or numerous (10⁵ to 10⁶), so O(log n) per query would be acceptable but O(1) is nicer.
You need both max − min or the ratio of two range statistics for many ranges (two tables).
A method that repeatedly asks “what is the minimum of this stretch?” inside another loop, such as a two-pointer window over a static array.
A related technique: the lowest common ancestor of two tree nodes reduces to a range minimum over an Euler tour, answered with a sparse table.

Look elsewhere when

The array changes: segment tree.

Worked problem

Spread of a range

The problem

Given an array and many queries (l, r), print for each the difference between the largest and smallest value in positions l to r (inclusive).

The array never changes, and the statistics are a maximum and a minimum: both idempotent.
Build one sparse table for max and one for min.
Each query is two O(1) lookups in each table and one subtraction.

python

from math import gcd

class SparseTable:
    def __init__(self, a, op=min):
        self.op = op
        n = len(a)
        self.t = [list(a)]                       # t[k][i] = op over a[i .. i + 2^k - 1]
        k = 1
        while (1 << k) <= n:
            prev = self.t[k - 1]
            half =  << (k - )
            self.t.([(prev[i], prev[i + half])  i  (n - ( << k) + )])
            k += 

     (self, l, r):                       
        k = (r - l + ).() -          
         self.(self.t[k][l], self.t[k][r - ( << k) + ])

 (a, queries):
    lo, hi = (a, min), (a, max)
     [hi.(l, r) - lo.(l, r)  l, r  queries]

(([, , , , , , , ], [(, ), (, ), (, ), (, )]))   
(([], [(, )]))

Worked problem

Longest stretch whose values stay within d

The problem

Given an array and a number d, find the length of the longest contiguous stretch in which the largest value minus the smallest value is at most d.

Use a two-pointer window: extend the right end r one step at a time; while the window's max − min exceeds d, move the left end l forward.
Each check of max − min over [l, r] is a range query on a static array: two sparse tables answer it in O(1).
Both pointers only move forward, so there are O(n) checks in total.

python

from math import gcd

class SparseTable:
    def __init__(self, a, op=min):
        self.op = op
        n = len(a)
        self.t = [list(a)]                       
        k = 
         ( << k) <= n:
            prev = self.t[k - ]
            half =  << (k - )
            self.t.([(prev[i], prev[i + half])  i  (n - ( << k) + )])
            k += 

     (self, l, r):                       
        k = (r - l + ).() -          
         self.(self.t[k][l], self.t[k][r - ( << k) + ])

 (a, d):
    lo, hi = (a, min), (a, max)
    best = 
    l = 
     r  ((a)):
         hi.(l, r) - lo.(l, r) > d:
            l += 
        best = (best, r - l + )
     best

(([, , , ], ))   
(([, , , , , ], ))   
(([], ))

Wrap-up

Remember this

A sparse table stores answers only for blocks whose length is a power of two, about n log n values in all.
Any range is covered by two (possibly overlapping) blocks of the largest power of two that fits, so a query is two lookups.
Overlap is harmless for idempotent operations (min, max, gcd) but double-counts sums.
Build costs O(n log n); queries are O(1); it only suits data that never changes.
Choose among prefix sums, sparse table, Fenwick tree and segment tree by two questions: does the data change, and is the operation undoable or idempotent?

Cheat sheet

Table: t[k][i] = op over a[i .. i + 2^k − 1]; t[k] built from t[k−1]
Query [l, r]: k = (r − l + 1).bit_length() − 1; op(t[k][l], t[k][r − 2^k + 1])
Needs: idempotent op (min, max, gcd, and, or) and static data
Cost: build O(n log n) time and space; query O(1)
Not for: sums (double counting) or changing data
Pairs well with: two pointers, LCA via Euler tour

Top traps to avoid

Using a sparse table for range sums or counts in O(1).
Computing k with floating-point log2 and rounding wrongly.
Second block starting at r − 2^k instead of r − 2^k + 1.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the time of one range-minimum query on a built sparse table?
2.Why can a sparse table use overlapping blocks for minimum but not for sums?
3.For a query on positions 1 to 6 (length 6), which power of two is used for the two blocks?
4.How many rows (levels) does the table for 8 values have, and how long is row 2?
5.“Answer 10⁶ queries for the maximum of a range in an array that is never modified” is best handled by:
6.What should you use if values in the array are updated between queries?
7.Sparse table (overlapping power-of-two blocks) for a = [5, 2, 8, 1, 9]. What is the minimum over [1, 4)?
8.Same sparse table: what is the minimum over [0, 2)?
9.Why can a sparse table answer a range query in O(1)?
10.What is the cost of building a sparse table on n values, and of one query?
11.Why does a sparse table work for min but not for range sums with overlap?
12.How many levels does a sparse table have for n = 8 (level 0 included)?
13.Sparse table on a = [5, 2, 8, 1, 9]: what is the minimum over the whole range [0, 5)?
14.When is a sparse table the right choice?
15.Can a sparse table answer range sums by overlapping two blocks?

from math import gcd

class SparseTable:
    def __init__(self, a, op=min):
        self.op = op
        n = len(a)
        self.t = [list(a)]                       # t[k][i] = op over a[i .. i + 2^k - 1]
        k = 1
        while (1 << k) <= n:
            prev = self.t[k - 1]
            half = 1 << (k - 1)
            self.t.append([op(prev[i], prev[i + half]) for i in range(n - (1 << k) + 1)])
            k += 1

    def query(self, l, r):                       # inclusive positions l..r
        k = (r - l + 1).bit_length() - 1         # largest k with 2^k <= length
        return self.op(self.t[k][l], self.t[k][r - (1 << k) + 1])

a = [5, 2, 6, 1, 7, 3, 8, 4]
sp = SparseTable(a)
print(sp.query(1, 6))   # 1
print(sp.query(5, 7))   # 3
print(sp.query(4, 4))   # 7
print(len(sp.t), [len(row) for row in sp.t])   # 4 [8, 7, 5, 1]
print(SparseTable(a, max).query(2, 5))   # 7
g = SparseTable([12, 18, 24, 36], gcd)
print(g.query(0, 3), g.query(1, 2), g.query(2, 3))   # 6 6 12

Sparse Table

After this lesson you will be able to

Builds on

Unlocks

Two overlapping mileposts

Precompute every possible answer

Only powers of two are needed, because overlap is harmless

How the table is organised

Building the table and answering two queries

The table for [5, 2, 6, 1, 7, 3, 8, 4], by hand

A sparse table class

Check it against brute force

Why sums are different

Costs and comparison with the other tools

Edge cases

Mistakes to avoid

How to spot a sparse-table problem

Spread of a range

Longest stretch whose values stay within d

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core1 problem

Application1 problem

Reading the code

Reading the code

Reading the code