Segment tree is a data structure to perform efficient range queries over an array.
Properties of the segment tree with the size N.
| Operation | Time complexity |
|---|---|
| build | O(N) |
| query | O(Log[N]) |
| update | O(Log[N]) |
- Implements classical data structure to deal with interval queries.
- Includes two classes IntSegmentTree and FloatSegmentTree implemented in pure C. They can boost performance up to 20x and are used by default for simple data types if possible.
$ pip install pysegmenttree
>> from pysegmenttree import stree
# Build the tree
# 'sum' function is used by default
>> tree = stree([5, 1, 9, 4, 5, 11])
# Find sum on the interval [1, 4)
>> tree.query(1, 4)
14
# Set element with index 3 to 6
>> tree.update(3, 6)
>> tree.query(1, 4)
16
There are three predefined query functions available that can be used with int or float trees. Use them as follows:
>> from pysegmenttree import stree, QueryFunction
>> tree = stree([5, 1, 9, 4, 5, 11], func=QueryFunction.MIN)
# Find min on the interval [1, 4)
>> tree.query(1, 4)
1
Plain python functions are also suitable, but in this case c-extensions will not be used.
>> tree = stree([5, 1, 9, 4, 5, 11], func=min)
>> tree.query(1, 4)
1
Example with user-defined class.
>> from pysegmenttree import stree
>> from pysegmenttree.test_utils import Vec2D
# List of 2D vectors
>> tree = stree([Vec2D(0, 1), Vec2D(5, -2), Vec2D(-2, 3)], func=max)
# Find the vector of maximum length on the interval [0, 2)
>> tree.query(0, 2)
Vec2D(x=5, y=-2)
Docs are available here.
Three basic segment tree operations were benchmarked for three different types int, float and Vec2D.
I included results for 3 other python segment trees libraries for comparison.
All code related to benchmarking can be found in benchmarks subdirectory.
| Param | Value |
|---|---|
| Tree size | 100 000 |
| Param | Value |
|---|---|
| Tree size | 100 000 |
| Queries performed | 10 000 |
| Param | Value |
|---|---|
| Tree size | 100 000 |
| Updates performed | 10 000 |
Read more here.