Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Sparse Table (Range Minimum Query)
Bookmark
Input
Standard
Small
Large
Left Range
Full Range
Custom
arr
=
[1, 3, 4, 8, 6, 1, 4, 2]
,
queryL
=
2
,
queryR
=
6
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
1
3
4
8
6
1
4
2
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
1
3
4
8
6
1
4
2
1
3
4
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
1
3
4
8
6
1
4
2
1
3
4
6
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
j=2
2²=4
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
j=2
2²=4
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
1
3
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
j=2
2²=4
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
1
3
1
1
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
j=2
2²=4
j=3
2³=8
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
1
3
1
1
1
1
arr
1
0
3
1
4
2
8
3
6
4
1
5
4
6
2
7
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
j=0
2⁰=1
j=1
2¹=2
j=2
2²=4
j=3
2³=8
1
3
4
8
6
1
4
2
1
3
4
6
1
1
2
1
3
1
1
1
1
Answer = 1
algo
master
.
io
Step:
Start: Build a Sparse Table for array of size 8, then answer RMQ(2, 6).
0 / 35
Input
Standard
Small
Large
Left Range
Full Range
Custom
arr
=
[1, 3, 4, 8, 6, 1, 4, 2]
,
queryL
=
2
,
queryR
=
6
0 / 35
algo
master
.
io
Step:
Start: Build a Sparse Table for array of size 8, then answer RMQ(2, 6).
