Metadata-Version: 1.2
Name: segment_tree
Version: 0.3.0
Summary: Multidimensional segment tree with ranges updates.
Home-page: https://github.com/evgeth/segment_tree
Author: Evgeny Yurtaev
Author-email: eugene@yurtaev.com
License: MIT
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`` operations
        -  Extensible to support more semigroup operations
        -  Python 2 is not currently supported
        
        Installation
        ============
        
        ``pip3 install segment-tree``
        
        Segment Tree (one-dimensional)
        ==============================
        
        Basic usage
        -----------
        
        .. code:: python
        
        
                from segment_tree import *
                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
        
                from segment_tree import *
                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
        
        Multidimensional Segment Tree example usage (alpha version, might have bugs)
        ============================================================================
        
        Basic usage
        -----------
        
        .. code:: python
        
                from segment_tree import *
                a = [[[1, 2], [1, 3]], [[-1, -2], [-1, -3]]]
                tree = MultidimensionalSegmentTree(a)
        
                tree.query([(0, 1), (0, 0), (0, 0)], max) # 1
                tree.query([(1, 1), (0, 1), (0, 1)], sum) # -7
                tree.query([(0, 1), (1, 1), (0, 1)], min) # -3
        
        Tests
        =====
        
        Execute ``python3 setup.py test`` to run tests.
        
Keywords: segment,tree,range,rmq,multidimensional
Platform: UNKNOWN
Requires-Python: >=3
