# pysegmenttree¶

**Segment tree** is a data structure to perform efficient range queries over an array.

For example, finding the sum/minimum/maximum of the arbitrary continuous interval in O(Log[N]) time. Logariphmic time complexity is achieved by storing the original input data in a tree like data structure with some additional precalculated data.

This library implementation is primarly inspired by this beatiful article.

## Library installation¶

```
$ pip install pysegmenttree
```

## Quick Start¶

```
>> 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
```

## Advanced usage¶

There are three predefined query functions available (`QueryFunction`

) that can be used with int or float trees.

```
>> 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 with them c-extensions will **not** be used.

```
# Warning! A slow version of segment tree will be used.
>> tree = stree([5, 1, 9, 4, 5, 11], func=min)
>> tree.query(1, 4)
1
```

Example with user-defined class `Vec2D`

.

```
>> 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)
```

## Methods complexity¶

Considering that input array has N elements.

Method |
Time complexity |
Space complexity |
---|---|---|

constructor |
O(N) |
O(2*N) |

query |
O(Log[N]) |
O(1) |

update |
O(Log[N]) |
O(1) |

## Source code¶

The project is hosted on GitHub.