{
    "info": {
        "author": "Chuancong Gao",
        "author_email": "chuancong@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Operating System :: OS Independent",
            "Programming Language :: Python",
            "Programming Language :: Python :: 2",
            "Programming Language :: Python :: 3"
        ],
        "description": "[![PyPI version](https://img.shields.io/pypi/v/RangeMinQuery.svg)](https://pypi.python.org/pypi/RangeMinQuery/)\n[![PyPI pyversions](https://img.shields.io/pypi/pyversions/RangeMinQuery.svg)](https://pypi.python.org/pypi/RangeMinQuery/)\n[![PyPI license](https://img.shields.io/pypi/l/RangeMinQuery.svg)](https://pypi.python.org/pypi/RangeMinQuery/)\n\nThis data structure solves the [range minimum query problem](https://en.wikipedia.org/wiki/Range_minimum_query) 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.\n\n# Installation\n\nThis package is available on PyPI. Just use `pip install -U RangeMinQuery` to install it. Then you can import it using `from RangeMinQuery import SegmentTree`.\n\n# Usage\n\n## Initialization\n\nUse `SegmentTree()` to initialize the tree with a set of keys, in **comparable and hashable** type.\n\n- `func=min` specifies how the best value is computed for any range of keys.\n\n- `default=None` specifies the default value for each key.\n\n- `maxChildNum=2` specifies the maximum number of children for each node.\n\n```Python\ntree = SegmentTree(\n    {1, 2, 3, 4, 5},\n    func=min, default=0, maxChildNum=2\n)\n```\n\nThe space complexity should be $O(n)$.\n\n## Updating\n\nYou 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.\n\n```Python\ntree.update({1: 3, 4: 6})\n```\n\nGiven m values updated, the time complexity should be $O(m^2)$.\n\n## Querying\n\nUse `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.\n\n```Python\ntree.query((1, 3))\n```\n\nThe time complexity should be $O(log n)$.",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "https://github.com/chuanconggao/RangeMinQuery/tarball/0.2",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/chuanconggao/RangeMinQuery",
        "keywords": "range-minimum-query",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "RangeMinQuery",
        "package_url": "https://pypi.org/project/RangeMinQuery/",
        "platform": "",
        "project_url": "https://pypi.org/project/RangeMinQuery/",
        "project_urls": {
            "Download": "https://github.com/chuanconggao/RangeMinQuery/tarball/0.2",
            "Homepage": "https://github.com/chuanconggao/RangeMinQuery"
        },
        "release_url": "https://pypi.org/project/RangeMinQuery/0.2/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Solving the Range Minimum Query problem",
        "version": "0.2"
    },
    "last_serial": 3826628,
    "releases": {
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "38745ac967566ede4c5442bd403d588a",
                    "sha256": "0468c6add969d20a8d8411dfb139096836859ee0aa0f352eb877505ed8553802"
                },
                "downloads": -1,
                "filename": "RangeMinQuery-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "38745ac967566ede4c5442bd403d588a",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 1805,
                "upload_time": "2017-05-27T20:07:17",
                "url": "https://files.pythonhosted.org/packages/37/bf/cdb31098aa84923c8e067af21385a851f937d927c9e3480eaa4515618a8b/RangeMinQuery-0.1.1.tar.gz"
            }
        ],
        "0.1.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "265aa14e1b2fbafceb6a73aeead8907a",
                    "sha256": "02109da8dc8908fddff5a100fd4cab222968fabaac7dace15a1a5934a5724a48"
                },
                "downloads": -1,
                "filename": "RangeMinQuery-0.1.2.tar.gz",
                "has_sig": false,
                "md5_digest": "265aa14e1b2fbafceb6a73aeead8907a",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 2602,
                "upload_time": "2018-03-03T19:14:23",
                "url": "https://files.pythonhosted.org/packages/34/73/938b2c033770ce34d6ca59296469c07bb08334479ab36fb7b18e0a90fd6a/RangeMinQuery-0.1.2.tar.gz"
            }
        ],
        "0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "53b85b5c930015647453fa7986b9d2ee",
                    "sha256": "8bb003ebd601860398f235049a085057f9cbe6f166c70e9f4a879042c96d80a6"
                },
                "downloads": -1,
                "filename": "RangeMinQuery-0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "53b85b5c930015647453fa7986b9d2ee",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 2968,
                "upload_time": "2018-05-02T10:59:14",
                "url": "https://files.pythonhosted.org/packages/ca/35/678a6bd7ac444db73d4da5ae16692f38a5f6c0a7b8a4a8242c32df441b3f/RangeMinQuery-0.2.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "53b85b5c930015647453fa7986b9d2ee",
                "sha256": "8bb003ebd601860398f235049a085057f9cbe6f166c70e9f4a879042c96d80a6"
            },
            "downloads": -1,
            "filename": "RangeMinQuery-0.2.tar.gz",
            "has_sig": false,
            "md5_digest": "53b85b5c930015647453fa7986b9d2ee",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 2968,
            "upload_time": "2018-05-02T10:59:14",
            "url": "https://files.pythonhosted.org/packages/ca/35/678a6bd7ac444db73d4da5ae16692f38a5f6c0a7b8a4a8242c32df441b3f/RangeMinQuery-0.2.tar.gz"
        }
    ]
}