RavensMove

Sparse Table Visualizer

Build a sparse table for static range minimum or maximum queries, then inspect the two power-of-two blocks used for an O(1) answer.

Values
9
Levels
4
Block
4
Result
0

Sparse table input

Range query

Step controls

Step 1 of 5: Start minimum query [2, 7] with length 6.

Sparse table levels

Start minimum query [2, 7] with length 6.

Query blocks Inside range
k = 0, length = 1
[0, 0]
7
[1, 1]
2
[2, 2]
3
[3, 3]
0
[4, 4]
5
[5, 5]
10
[6, 6]
3
[7, 7]
12
[8, 8]
18
k = 1, length = 2
[0, 1]
2
[1, 2]
2
[2, 3]
0
[3, 4]
0
[4, 5]
5
[5, 6]
3
[6, 7]
3
[7, 8]
12
k = 2, length = 4
[0, 3]
0
[1, 4]
0
[2, 5]
0
[3, 6]
0
[4, 7]
3
[5, 8]
3
k = 3, length = 8
[0, 7]
0
[1, 8]
0

Array view

0
7
1
2
2
3
3
0
4
5
5
10
6
3
7
12
8
18

Query summary

mode = min
range = [2, 7]
k = 2
block length = 4
blocks = [2, 5] and [4, 7]
result = 0

Trace

Step 1. Start minimum query [2, 7] with length 6.
Step 2. Use k = floor(log2(6)) = 2, so each block has length 4.
Step 3. Read the left block [2, 5] = 0.
Step 4. Read the right block [4, 7] = 3.
Step 5. Answer = min(0, 3) = 0.

What is a Sparse Table Visualizer?

A sparse table visualizer shows how static range minimum or maximum queries can be answered using precomputed power-of-two blocks.

This tool builds each table level from an input array. For a query [left, right], it chooses k = floor(log2(length)), reads the block starting at left, reads the block ending at right, and combines those two values.

For the full cluster of related pages, browse the Data Structure Visualizers hub.

How to use this sparse table visualizer

  • Paste an array of whole numbers.
  • Choose minimum or maximum mode.
  • Choose the left and right indexes for a static range query.
  • Run the query to highlight the two power-of-two blocks.
  • Compare each table level with the ranges it precomputes.

Sparse table complexity

Sparse tables build in O(n log n) time and use O(n log n) space. After preprocessing, range minimum and range maximum queries run in O(1) time because the answer is formed from two overlapping blocks.

Use the Segment Tree Visualizer or Fenwick Tree Visualizer when values need to change after preprocessing.

Frequently Asked Questions

What operations work with a sparse table?
Sparse tables work best for idempotent operations such as minimum, maximum, and greatest common divisor.
Why does a sparse table use overlapping blocks?
For idempotent operations, overlapping values do not change the answer, so two power-of-two blocks can cover any query range.
Can a sparse table handle updates?
Sparse tables are designed for static arrays. If values change often, use a segment tree or Fenwick tree instead.
What does each sparse table level mean?
Level `k` stores answers for every range of length `2^k`.

Related tools

Binary Search Tree Visualizer Visualize binary search tree operations online. Paste an insertion-order array, render the BST, and run search, delete, insert, and traversal steps.Binary Search Visualizer Visualize binary search online. Paste a sorted array, choose exact search or lower bound, and inspect low, high, mid, comparisons, and result index.Prefix Sum Visualizer Visualize prefix sum arrays online. Paste values, build cumulative sums step by step, choose a range, and inspect how range sum queries work.