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.