AlgoScope

Sparse Table

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

Data structures, data structure, advanced
Row 2^1, column 0: min of 5 and 2 is 2.012345672^02^12^22^3524713682
Row 2^1, column 0: min of 5 and 2 is 2.012345672^02^12^22^3524713682

Sparse Table: Build over eight values

Decision, step 2 of 7

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.

Cost

Build
O(n log n)
Query
O(1)
Space
O(n log n)

Static. No updates.

Leads to

Topics that need this one first.

Taught by the same lesson

Sparse Table covers these too, in the same run.