data_structures.arrays.sparse_table

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)

Wikipedia link: https://en.wikipedia.org/wiki/Range_minimum_query

Functions

build_sparse_table(→ list[list[int]])	Precompute range minimum queries with power of two length and store the precomputed
query(→ int)

Module Contents

data_structures.arrays.sparse_table.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

data_structures.arrays.sparse_table.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