SparseTable

class pydatastructs.SparseTable(array, func)

Represents the sparse table data structure.

Parameters

• array (OneDimensionalArray) – The array to be used for filling the sparse table.

• func (callable) –

  The function to be used for filling the sparse table. It should accept only one tuple as an argument. The size of the tuple will be either 1 or 2 and any one of the elements can be None. You can treat None in whatever way you want. For example, in case of minimum values, None can be treated as infinity. We provide the following which can be used as an argument value for this parameter,

  minimum - For range minimum queries.

  greatest_common_divisor - For queries finding greatest

  common divisor of a range.

  summation - For range sum queries.

Examples

>>> from pydatastructs import SparseTable, minimum
>>> from pydatastructs import OneDimensionalArray
>>> arr = OneDimensionalArray(int, [1, 2, 3, 4, 5])
>>> s_t = SparseTable(arr, minimum)
>>> str(s_t)
"['[1, 1, 1]', '[2, 2, 2]', '[3, 3, None]', '[4, 4, None]', '[5, None, None]']"

References

1

https://cp-algorithms.com/data_structures/sparse-table.html

query(start, end)

Method to perform a query on sparse table in [start, end) range.

Parameters

• start (int) – The starting index of the range.

• end (int) – The ending index of the range.

__str__()

Return str(self).

func

__module__ = 'pydatastructs.miscellaneous_data_structures.sparse_table'