LazySegmentTreeBase

template<class NodeType, class PromiseType, class FinalType>
class LazySegmentTreeBase : public SegmentTreeBase<NodeType, FinalType>

Tree that supports lazily applying an operation to range.

Each inner node has a promise value describing an operation that needs to be applied to corresponding subtree.

Child classes are expected to implement to pushDown(size_t nodePosition) method. Which applies the applies the operation stored in promise for nodePosition to the direct children nodes.

  • tparam NodeType

    type of tree nodes

    tparam PromiseType

    type describing operation that needs to be applied to subtree

    tparam FinalType

    child class type for CRTP. See SegmentTreeBase

Public Functions

  • inline LazySegmentTreeBase(size_t size, const PromiseType &neutralPromise)

    • Parameters

      • size – Number of tree leaves.

      • neutralPromise – Promise value that doesn’t modify tree nodes.

  • inline LazySegmentTreeBase(size_t size, NodeType value, PromiseType neutralPromise)

  • inline NodeType rangeOperation(size_t l, size_t r, NodeType initialValue)

    Calculate the tree operation over the range [l, r)

    • Parameters

      • l – inclusive range left side

      • r – exclusive range right side

      • initialValue – Initial value for aggregate operation.

      Returns

      Tree operation calculated over the range.