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") # -1Updates 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") # 2Multidimensional 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) # -3Tests
Execute python3 setup.py test to run tests.
1 maintainer
Metadata
1 maintainer
Release files for segment-tree 0.3.2
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| segment_tree-0.3.2.tar.gz | 4.2 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| segment_tree-0.3.2-py3-none-any.whl | Python 3 | none | any | Details |
Total release size: 11.0 kB
Release files / segment_tree-0.3.2.tar.gz
| Download URL | segment_tree-0.3.2.tar.gz |
|---|---|
| Size | 4.2 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
591941461e89a26d3b16ae5c271c7057d56b2efcbbf598b8c56f4131abe7deea
|
|
BLAKE2b-256 checksum How to use checksums |
4cf775b9a6242357597233f4ad34d9382d6a88118ebf8609058a67f7f694c174
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
Release files / segment_tree-0.3.2-py3-none-any.whl
| Download URL | segment_tree-0.3.2-py3-none-any.whl |
|---|---|
| Size | 6.8 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
408e320a624ba7470f0ba3dd19539e91974c496c8c4ded1aba193c08d765ba64
|
|
BLAKE2b-256 checksum How to use checksums |
4cbc291bc465c23e36830c35ddda9cc973ca77095f2bc8c0f49d7df157d2f3c3
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
