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.
Sparse 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.
Cost
- Build
- O(n log n)
- Query
- O(1)
- Space
- O(n log n)
Static. No updates.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Sparse Table covers these too, in the same run.