ds-kit-js - v1.1.0
    Preparing search index...

    Class SegmentTree<T>

    Дерево отрезков для произвольной ассоциативной операции (сумма, минимум, максимум, НОД…). Изменение элемента и запрос на отрезке — O(log n), построение — O(n). Операция не обязана быть коммутативной: порядок элементов сохраняется.

    Отрезки задаются полуинтервалом [from, to), как в Array#slice.

    const tree = SegmentTree.min([5, 2, 8, 1, 9]);
    tree.query(0, 3); // 2
    tree.set(1, 7);
    tree.query(0, 3); // 5

    Type Parameters

    • T
    Index
    constructor
    size
    sum min max query set get toArray

    • Type Parameters

      • T

      Parameters

      • values: readonly T[]

        Исходный массив.

      • combine: (a: T, b: T) => T

        Ассоциативная операция.

      • identity: T

        Нейтральный элемент операции (0 для суммы, Infinity для минимума…).

      Returns SegmentTree<T>

    • Результат операции на полуинтервале [from, to). Для пустого отрезка — identity.

      Parameters

      • from: number = 0
      • to: number = ...

      Returns T

    • Заменяет элемент по индексу.

      Parameters

      • index: number
      • value: T

      Returns void

    • Элемент по индексу.

      Parameters

      • index: number

      Returns T

    Settings
    Member Visibility

    On This Page
    Constructors
    Accessors
    Methods