#### Sparse Table

p
```"""
Sparse table is a data structure that allows answering range queries on
a static number list, i.e. the elements do not change throughout all the queries.

The implementation below will solve the problem of Range Minimum Query:
Finding the minimum value of a subset [L..R] of a static number list.

Overall time complexity: O(nlogn)
Overall space complexity: O(nlogn)

"""

from math import log2

def build_sparse_table(number_list: list[int]) -> list[list[int]]:
"""
Precompute range minimum queries with power of two length and store the precomputed
values in a table.

>>> build_sparse_table([8, 1, 0, 3, 4, 9, 3])
[[8, 1, 0, 3, 4, 9, 3], [1, 0, 0, 3, 4, 3, 0], [0, 0, 0, 3, 0, 0, 0]]
>>> build_sparse_table([3, 1, 9])
[[3, 1, 9], [1, 1, 0]]
>>> build_sparse_table([])
Traceback (most recent call last):
...
ValueError: empty number list not allowed
"""
if not number_list:
raise ValueError("empty number list not allowed")

length = len(number_list)
# Initialise sparse_table -- sparse_table[j][i] represents the minimum value of the
# subset of length (2 ** j) of number_list, starting from index i.

# smallest power of 2 subset length that fully covers number_list
row = int(log2(length)) + 1
sparse_table = [[0 for i in range(length)] for j in range(row)]

# minimum of subset of length 1 is that value itself
for i, value in enumerate(number_list):
sparse_table[0][i] = value
j = 1

# compute the minimum value for all intervals with size (2 ** j)
while (1 << j) <= length:
i = 0
# while subset starting from i still have at least (2 ** j) elements
while (i + (1 << j) - 1) < length:
# split range [i, i + 2 ** j] and find minimum of 2 halves
sparse_table[j][i] = min(
sparse_table[j - 1][i + (1 << (j - 1))], sparse_table[j - 1][i]
)
i += 1
j += 1
return sparse_table

def query(sparse_table: list[list[int]], left_bound: int, right_bound: int) -> int:
"""
>>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 0, 4)
0
>>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 4, 6)
3
>>> query(build_sparse_table([3, 1, 9]), 2, 2)
9
>>> query(build_sparse_table([3, 1, 9]), 0, 1)
1
>>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 0, 11)
Traceback (most recent call last):
...
IndexError: list index out of range
>>> query(build_sparse_table([]), 0, 0)
Traceback (most recent call last):
...
ValueError: empty number list not allowed
"""
if left_bound < 0 or right_bound >= len(sparse_table[0]):
raise IndexError("list index out of range")

# highest subset length of power of 2 that is within range [left_bound, right_bound]
j = int(log2(right_bound - left_bound + 1))

# minimum of 2 overlapping smaller subsets:
# [left_bound, left_bound + 2 ** j - 1] and [right_bound - 2 ** j + 1, right_bound]
return min(sparse_table[j][right_bound - (1 << j) + 1], sparse_table[j][left_bound])

if __name__ == "__main__":
from doctest import testmod

testmod()
print(f"{query(build_sparse_table([3, 1, 9]), 2, 2) = }")
```