sparse_table.py

"""
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
"""

frommathimportlog2


defbuild_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
 """
ifnotnumber_list:
raiseValueError("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= [[0foriinrange(length)] forjinrange(row)]

# minimum of subset of length 1 is that value itself
fori, valueinenumerate(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
returnsparse_table


defquery(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
 """
ifleft_bound<0orright_bound>=len(sparse_table[0]):
raiseIndexError("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]
returnmin(sparse_table[j][right_bound- (1<<j) +1], sparse_table[j][left_bound])


if__name__=="__main__":
fromdoctestimporttestmod

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