Skip to main content

Solving the Range Minimum Query problem

Project description

PyPI version PyPI pyversions PyPI license

This data structure solves the range minimum query problem of finding the minimal value in a sub-array of an array of comparable objects. Different from the original problem, this data structure also supports updating the values.

Installation

This package is available on PyPI. Just use pip install -U RangeMinQuery to install it. Then you can import it using from RangeMinQuery import SegmentTree.

Usage

Initialization

Use SegmentTree() to initialize the tree with a set of keys, in comparable and hashable type.

  • func=min specifies how the best value is computed for any range of keys.

  • default=None specifies the default value for each key.

  • maxChildNum=2 specifies the maximum number of children for each node.

tree = SegmentTree(
    {1, 2, 3, 4, 5},
    func=min, default=0, maxChildNum=2
)

The space complexity should be $O(n)$.

Updating

You need to use update() to initialize the values, or update the values if necessary, by specifying a dictionary of key/value pairs. Currently, adding new keys is not supported yet.

tree.update({1: 3, 4: 6})

Given m values updated, the time complexity should be $O(m^2)$.

Querying

Use query() to to find the best value of a range of keys. The range is denoted by a tuple (a, b), representing each key x such that a <= x < b. The range here is closed on the left side and open on the right side, consistent with Python tradition.

tree.query((1, 3))

The time complexity should be $O(log n)$.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for RangeMinQuery, version 0.2
Filename, size File type Python version Upload date Hashes
Filename, size RangeMinQuery-0.2.tar.gz (3.0 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page