data_structures.arrays.sparse_table
===================================

.. py:module:: data_structures.arrays.sparse_table

.. autoapi-nested-parse::

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

.. autoapisummary::

   data_structures.arrays.sparse_table.build_sparse_table
   data_structures.arrays.sparse_table.query


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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