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.
- 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.