Show / Hide Table of Contents

    Class SegmentTree<T>

    A segment tree implementation.

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

    Constructors

    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

    GetEnumerator()

    Declaration
    public IEnumerator<T> GetEnumerator()
    Returns
    Type Description
    IEnumerator<T>

    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
    Back to top Generated by DocFX