Sparse Table

Data structureadvancedRange Structures

Row k holds the minimum of every window of length 2^k, each from two half windows above: O(n log n) once.

Decision · step 2 of 7Sparse Table: Build over eight values

Row 2^1 covers windows of length 2. Cell 0 is the minimum of two windows of length 1 from the row above: 5 at column 0 and 2 at column 1, so min = 2. Together they are exactly the values from index 0 to 1.

Open in the player →or start at step 2

What you will see

Rows for lengths 1, 2, 4, ...; a query overlays two blocks that cover the range.

How sparse table works →

Cost

build	`O(n log n)`
query	`O(1)`
Space	`O(n log n)`

Static; no updates.

How you work with it here

play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.

Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.

Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.

Before this

Matrix Range Minimum Query

Segment Tree

Leads to

Topics that need this one first.

Sparse Table Build and Query

Taught by the same lesson

Sparse Table covers these too, in the same run.