Metadata-Version: 2.0
Name: segment-tree
Version: 0.2.2
Summary: The most comprehensive implementation of Segment Tree.
Home-page: https://github.com/evgeth/segment_tree
Author: Evgeny Yurtaev
Author-email: eugene@yurtaev.com
License: MIT
Keywords: segment,tree,range,rmq
Platform: UNKNOWN
Requires-Python: >=3

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.


