Sparse Table Build and Query
k = floor(log2(len)); the answer is min of the windows starting at l and ending at r, overlap harmless.
Decision · step 2 of 4Sparse Table: Query with overlapping windows
5 values fit a window of length 4 = 2^2 and not of 8, so k = 2: use row 2^2.
What you will see
Rows for each power of two; a query highlights two overlapping blocks.
Cost
| Best | O(1) |
|---|---|
| Average | O(1) |
| Worst | O(1) |
| Space | O(n log n) |
O(n log n) build.
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: Structure nodes announce the range they cover and their value; each step announces which nodes answer the query.
Reduced motion: Contributing nodes highlight statically; no path animation.