The most comprehensive implementation of Segment Tree.
Project description
Segment Tree with range operations
==================================
.. figure:: https://img.shields.io/badge/license-MIT-blue.svg
:alt: LicenseLink
LicenseLink
This is a general implementation of a segment tree for Python 3.
- Semigroup range operations in O(logN) time
- Built-in support for ``max``, ``min``, ``sum`` functions
- Extensible to support more semigroup operations
- Only Python 3 for now
Example usage
=============
Basic queries
-------------
.. code:: python
array = [3, 1, 5, 3, 13, 7, 2, 7, 2]
tree = SegmentTree(array)
t.query(1, 3, "sum") # 9
t.update(0, 10) # [10, 1, 5, 3, 13, 7, 2, 7, 2]
t.query(0, 8, "min") # 0
t.update(2, -1) # [10, 1, -1, 3, 13, 7, 2, 0, 2]
t.query(0, 2, "min") # -1
Updates on ranges
-----------------
.. code:: python
array = [1, 2, 3, 4, 5]
t = SegmentTree(array)
t.update_range(0, 2, 6) # 6 6 6 4 5
t.update_range(1, 4, 2) # 6 2 2 2 2
t.query(0, 3, "min") # 2
Installation
============
``pip3 install segment-tree``
Supported operations and complexity
===================================
+---------+------------+--------------+----------+
| Functio | Descriptio | Complexity | Addition |
| n | n | | al |
| | | | storage |
+=========+============+==============+==========+
| ``Segme | Builds a | O(n log n) | O(n log |
| ntTree( | segment | | n) |
| array)` | tree from | | |
| ` | an | | |
| | ``array`` | | |
+---------+------------+--------------+----------+
| ``updat | Updates an | O(log n) | O(1) |
| e(posit | old value | | |
| ion, va | at | | |
| lue)`` | ``position | | |
| | `` | | |
| | to | | |
| | ``value`` | | |
+---------+------------+--------------+----------+
| ``updat | Sets | O(log n) | O(1) |
| e_range | ``value`` | | |
| (start, | on a | | |
| end, v | ``[start, | | |
| alue)`` | end]`` | | |
| | range | | |
+---------+------------+--------------+----------+
| ``query | Returns | O(log n) | O(1) |
| (start, | ``function | | |
| end, f | ([start, e | | |
| unction | nd])`` | | |
| )`` | | | |
+---------+------------+--------------+----------+
Tests
=====
Execute ``python3 setup.py test`` to run tests.
==================================
.. figure:: https://img.shields.io/badge/license-MIT-blue.svg
:alt: LicenseLink
LicenseLink
This is a general implementation of a segment tree for Python 3.
- Semigroup range operations in O(logN) time
- Built-in support for ``max``, ``min``, ``sum`` functions
- Extensible to support more semigroup operations
- Only Python 3 for now
Example usage
=============
Basic queries
-------------
.. code:: python
array = [3, 1, 5, 3, 13, 7, 2, 7, 2]
tree = SegmentTree(array)
t.query(1, 3, "sum") # 9
t.update(0, 10) # [10, 1, 5, 3, 13, 7, 2, 7, 2]
t.query(0, 8, "min") # 0
t.update(2, -1) # [10, 1, -1, 3, 13, 7, 2, 0, 2]
t.query(0, 2, "min") # -1
Updates on ranges
-----------------
.. code:: python
array = [1, 2, 3, 4, 5]
t = SegmentTree(array)
t.update_range(0, 2, 6) # 6 6 6 4 5
t.update_range(1, 4, 2) # 6 2 2 2 2
t.query(0, 3, "min") # 2
Installation
============
``pip3 install segment-tree``
Supported operations and complexity
===================================
+---------+------------+--------------+----------+
| Functio | Descriptio | Complexity | Addition |
| n | n | | al |
| | | | storage |
+=========+============+==============+==========+
| ``Segme | Builds a | O(n log n) | O(n log |
| ntTree( | segment | | n) |
| array)` | tree from | | |
| ` | an | | |
| | ``array`` | | |
+---------+------------+--------------+----------+
| ``updat | Updates an | O(log n) | O(1) |
| e(posit | old value | | |
| ion, va | at | | |
| lue)`` | ``position | | |
| | `` | | |
| | to | | |
| | ``value`` | | |
+---------+------------+--------------+----------+
| ``updat | Sets | O(log n) | O(1) |
| e_range | ``value`` | | |
| (start, | on a | | |
| end, v | ``[start, | | |
| alue)`` | end]`` | | |
| | range | | |
+---------+------------+--------------+----------+
| ``query | Returns | O(log n) | O(1) |
| (start, | ``function | | |
| end, f | ([start, e | | |
| unction | nd])`` | | |
| )`` | | | |
+---------+------------+--------------+----------+
Tests
=====
Execute ``python3 setup.py test`` to run tests.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
segment_tree-0.2.0.tar.gz
(3.0 kB
view hashes)
Built Distribution
Close
Hashes for segment_tree-0.2.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 465da3ab811956325d2bfb0b528eee55767b09bf8d3b7f1b2d130456859797f2 |
|
MD5 | dbdc976a9308f27b2ff594460e1c5940 |
|
BLAKE2b-256 | 239e25a497119105cbb7204a7b7d402f618b0f8bd965a7c2d28d4908f5a4978b |