segtree_tool¶

class xuance.common.segtree_tool.MinSegmentTree(capacity)[源代码]¶

基类：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)[源代码]¶

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

参数:

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

返回:

The minimum value in the specified range.

返回类型:

float

class xuance.common.segtree_tool.SegmentTree(capacity, operation, neutral_element)[源代码]¶

基类：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)[源代码]¶: Initializes the segment tree with a specified capacity, operation, and neutral element.

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

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

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

reduce(start=0, end=None)[源代码]¶

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

参数:

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

返回:

The result of the operation over the specified range.

返回类型:

Any

class xuance.common.segtree_tool.SumSegmentTree(capacity)[源代码]¶

基类：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)[源代码]¶

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

参数:: prefixsum (float) – The target prefix sum.
返回:: The index corresponding to the target prefix sum.
返回类型:: int
抛出:: AssertionError – If prefixsum is not within the valid range [0, total sum].

sum(start=0, end=None)[源代码]¶

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

参数:

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

返回:

The sum of elements in the specified range.

返回类型:

float