Algorithms

class pydatastructs.RangeQueryStatic(array, func, data_structure='sparse_table')

Produces results for range queries of different kinds by using specified data structure.

Parameters

  • array (OneDimensionalArray) – The array for which we need to answer queries. All the elements should be of type int.

  • func (callable) –

    The function to be used for generating results of a query. 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 according to the query you are performing. For example, in case of range minimum queries, 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.

  • data_structure (str) –

    The data structure to be used for performing range queries. Currently the following data structures are supported,

    ’array’ -> Array data structure.

    Each query takes O(end - start) time asymptotically.

    ’sparse_table’ -> Sparse table data structure.

    Each query takes O(log(end - start)) time asymptotically.

    By default, ‘sparse_table’.

Examples

>>> from pydatastructs import OneDimensionalArray, RangeQueryStatic
>>> from pydatastructs import minimum
>>> arr = OneDimensionalArray(int, [4, 6, 1, 5, 7, 3])
>>> RMQ = RangeQueryStatic(arr, minimum)
>>> RMQ.query(3, 4)
5
>>> RMQ.query(0, 4)
1
>>> RMQ.query(0, 2)
1

Note

The array once passed as an input should not be modified once the RangeQueryStatic constructor is called. If you have updated the array, then you need to create a new RangeQueryStatic object with this updated array.

query(end)

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

Parameters

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

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

__module__ = 'pydatastructs.miscellaneous_data_structures.algorithms'