LazySegmentTreeBase

    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

      child class type for CRTP. See SegmentTreeBase

    Public Functions

    • inline LazySegmentTreeBase(size_t size, const &neutralPromise)

      • Parameters

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

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

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