Multidimensional segment tree with ranges updates.
Project description
Segment Tree with range operations
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
Limited support for multidimensional trees
Python 2 is not currently supported
Installation
pip3 install segment-tree
Segment Tree (one-dimensional)
Basic usage
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
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 (alpha version, might have bugs)
Basic usage
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.
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.3.2.tar.gz
(4.2 kB
view hashes)
Built Distribution
Close
Hashes for segment_tree-0.3.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 408e320a624ba7470f0ba3dd19539e91974c496c8c4ded1aba193c08d765ba64 |
|
MD5 | 22ee041ae041a3755f51a19e720c7bc9 |
|
BLAKE2b-256 | 4cbc291bc465c23e36830c35ddda9cc973ca77095f2bc8c0f49d7df157d2f3c3 |