Class SegmentTree<T>

A segment tree implementation.

Inheritance
Object
SegmentTree<T>
Implements
Inherited Members
Namespace: Advanced.Algorithms.DataStructures
Assembly: Advanced.Algorithms.dll
Syntax
public class SegmentTree<T> : IEnumerable<T>, IEnumerable
Type Parameters
Name Description
T

Constructors

| Improve this Doc View Source

SegmentTree(T[], Func<T, T, T>, Func<T>)

Constructs a segment tree using the specified operation function. Operation function is the criteria for range queries. For example operation function can return Max, Min or Sum of the two input elements. Default value is the void value that will eliminate a node during operation comparisons. For example if operation return min value then the default value will be largest value (int.Max for if T is int). Or default value will be 0 if operation is sum. Time complexity: O(n).

Declaration
public SegmentTree(T[] input, Func<T, T, T> operation, Func<T> defaultValue)
Parameters
Type Name Description
T[] input
Func<T, T, T> operation
Func<T> defaultValue

Methods

| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type Description
IEnumerator<T>
| Improve this Doc View Source

RangeResult(Int32, Int32)

Gets the operation aggregated result for given range of the input. Time complexity: O(log(n)).

Declaration
public T RangeResult(int startIndex, int endIndex)
Parameters
Type Name Description
Int32 startIndex
Int32 endIndex
Returns
Type Description
T

Explicit Interface Implementations

| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
IEnumerator

Implements