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

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.