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.

Template Parameters

• NodeType – type of tree nodes

• PromiseType – type describing operation that needs to be applied to subtree

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