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.
Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|
Filename, size segment_tree-0.3.2-py3-none-any.whl (6.8 kB) | File type Wheel | Python version py3 | Upload date | Hashes View |
Filename, size segment_tree-0.3.2.tar.gz (4.2 kB) | File type Source | Python version None | Upload date | Hashes View |
Close
Hashes for segment_tree-0.3.2-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 408e320a624ba7470f0ba3dd19539e91974c496c8c4ded1aba193c08d765ba64 |
|
MD5 | 22ee041ae041a3755f51a19e720c7bc9 |
|
BLAKE2-256 | 4cbc291bc465c23e36830c35ddda9cc973ca77095f2bc8c0f49d7df157d2f3c3 |