module `emote.memory.segment_tree`

Classes

`class SegmentTree:`

Methods

def __init__(self, capacity, operation, neutral_element) -> None

Build a Segment Tree data structure. https://en.wikipedia.org/wiki/Segment_tree

Can be used as regular array, but with two important differences:

a) setting item's value is slightly slower.
   It is O(lg capacity) instead of O(1).
b) user has access to an efficient ( O(log segment size) )
   `reduce` operation which reduces `operation` over
   a contiguous subsequence of items in the array.

Arguments:

capacity: (int) Total size of the array - must be a power of two.
operation: (lambda (Any, Any): Any) operation for combining elements (eg. sum, max) must form a mathematical group together with the set of possible values for array elements (i.e. be associative)
neutral_element: (Any) neutral element for the operation above. eg. float('-inf') for max and 0 for sum.

def reduce(self, start, end) -> None

Returns result of applying self.operation to a contiguous subsequence of the array.

self.operation(arr[start], operation(arr[start+1], operation(... arr[end])))

Arguments:

start: (int) beginning of the subsequence
end: (int) end of the subsequences

Returns:

(Any) result of reducing self.operation over the specified range of array elements.

`class SumSegmentTree(SegmentTree):`

Methods

def __init__(self, capacity) -> None

def sum(self, start, end) -> None

Returns arr[start] + ... + arr[end]

Arguments:

start: (int) start position of the reduction (must be >= 0)
end: (int) end position of the reduction (must be < len(arr), can be None for len(arr) - 1)

Returns:

(Any) reduction of SumSegmentTree

def find_prefixsum_idx(self, prefixsum) -> None

Find the highest index i in the array such that sum(arr[0] + arr[1] + ... + arr[i - i]) <= prefixsum

if array values are probabilities, this function allows to sample indexes according to the discrete probability efficiently.

Arguments:

prefixsum: (float) upperbound on the sum of array prefix

Returns:

(int) highest index satisfying the prefixsum constraint

`class MinSegmentTree(SegmentTree):`

Methods

def __init__(self, capacity) -> None

def min(self, start, end) -> None

Returns min(arr[start], ..., arr[end])

Arguments:

start: (int) start position of the reduction (must be >= 0)
end: (int) end position of the reduction (must be < len(arr), can be None for len(arr) - 1)

Returns:

(Any) reduction of MinSegmentTree

Emote