Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 4:47
Sparse Table
A sparse table precomputes the answer for every window whose length is a power of two, level by level, in O(n log n) time and memory. For idempotent operations such as min, max and gcd, any range is covered by two overlapping blocks, so a query is O(1); sums need a greedy split into disjoint power-of-two blocks and cost O(log n). The table is for static data only: one update forces a rebuild.
You will learn
- Build a sparse table level by level with st[i][j] = f(st[i-1][j], st[i-1][j + 2^(i-1)]) and explain its O(n log n) time and memory
- Answer range min/max/gcd queries in O(1) with two overlapping power-of-two blocks and the floor of log2 from bit_width
- Explain why the overlap trick fails for sums and answer sum queries with the greedy O(log n) decomposition
- Size the table to the input, get the build loop bounds right, and recognise when data changes too often for a sparse table