LazySegmentTreeBase¶
-
template<class
NodeType
, classPromiseType
, classFinalType
>
classLazySegmentTreeBase
: 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.
- Template Parameters
NodeType
: type of tree nodesPromiseType
: type describing operation that needs to be applied to subtreeFinalType
: child class type for CRTP. See SegmentTreeBase
Public Functions
-
LazySegmentTreeBase
(size_t size, const PromiseType &neutralPromise)¶ - Parameters
size
: Number of tree leaves.neutralPromise
: Promise value that doesn’t modify tree nodes.
-
LazySegmentTreeBase
(size_t size, NodeType value, PromiseType neutralPromise)¶