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

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)
NodeType rangeOperation(size_t l, size_t r, NodeType initialValue)

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

Return

Tree operation calculated over the range.

Parameters

  • l: inclusive range left side

  • r: exclusive range right side

  • initialValue: Initial value for aggregate operation.