segtree_tool¶

class xuance.common.segtree_tool.MinSegmentTree(capacity)[source]¶

Bases: SegmentTree

A specialized implementation of a Segment Tree for range minimum queries.

_capacity¶

The size of the underlying array, must be a power of 2.

Type:: int

_value¶

The tree representation of the segment tree, storing intermediate minimums.

Type:: list

_operation¶

The operation to be performed (minimum in this case).

Type:: callable

_neutral_element¶

The neutral element for the operation (infinity for minimum).

Type:: float

min(start=0, end=None)[source]¶

Compute the minimum value in the range [start, end). Returns min(arr[start], …, arr[end])

Parameters:

start (int) – The starting index of the range (inclusive).
end (int, optional) – The ending index of the range (exclusive). Defaults to the full range.

Returns:

The minimum value in the specified range.

Return type:

float

class xuance.common.segtree_tool.SegmentTree(capacity, operation, neutral_element)[source]¶

Bases: object

A data structure for efficient range queries and point updates using a binary tree representation.

_capacity¶

The number of elements in the tree, must be a power of 2.

Type:: int

_value¶

Internal array to store the tree nodes.

Type:: list

_operation¶

A binary operation (e.g., addition, min, max) for range queries.

Type:: Callable

_neutral_element¶

The neutral element for the operation (e.g., 0 for addition, infinity for min).

Type:: Any

__init__(capacity, operation, neutral_element)[source]¶: Initializes the segment tree with a specified capacity, operation, and neutral element.

reduce(start=0, end=None)[source]¶: Computes the result of the operation over a range [start, end).

__setitem__(idx, val)[source]¶: Updates the value at a specific index and propagates changes.

__getitem__(idx)[source]¶: Retrieves the value at a specific index.

reduce(start=0, end=None)[source]¶

Computes the result of the operation over a range [start, end).

Parameters:

start (int, optional) – Start of the range (default is 0).
end (int, optional) – End of the range (default is the tree’s capacity).

Returns:

The result of the operation over the specified range.

Return type:

Any

class xuance.common.segtree_tool.SumSegmentTree(capacity)[source]¶

Bases: SegmentTree

A specialized implementation of a Segment Tree for summation queries and prefix-sum searches.

_capacity¶

The size of the underlying array, must be a power of 2.

Type:: int

_value¶

The tree representation of the segment tree, storing intermediate sums.

Type:: list

_operation¶

The operation to be performed (addition in this case).

Type:: callable

_neutral_element¶

The neutral element for the operation (0.0 for addition).

Type:: float

find_prefixsum_idx(prefixsum)[source]¶

Find the index of the smallest prefix sum greater than or equal to the given value.

Parameters:: prefixsum (float) – The target prefix sum.
Returns:: The index corresponding to the target prefix sum.
Return type:: int
Raises:: AssertionError – If prefixsum is not within the valid range [0, total sum].

sum(start=0, end=None)[source]¶

Compute the sum of elements in the range [start, end). Returns arr[start] + … + arr[end]

Parameters:

start (int) – The starting index of the range (inclusive).
end (int, optional) – The ending index of the range (exclusive). Defaults to the full range.

Returns:

The sum of elements in the specified range.

Return type:

float