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.