MinMaxAccumulateTree

template<class IntegerType>
class MinMaxAccumulateTree : public LazySegmentTreeBase<std::pair<IntegerType, IntegerType>, std::pair<IntegerType, IntegerType>, MinMaxAccumulateTree<IntegerType>>

Structure for keeping track of minimum and maximum value set at each position.

Supports range update and range query.

Example: 

MinMaxAccumulateTree t(30); // operate within range [0; 30)
t.updateRange(1, 5, 10);
rangeMinMax(0, 20);// -> {10, 10}
t.updateRange(4, 6, 15);
t.updateRange(3, 10, 20);
t.rangeMinMax(0, 20); // -> {10, 20}
t.rangeMinMax(1, 3); // -> {10, 10}
t.rangeMinMax(5, 8); // -> {15, 20}

Public Functions

inline MinMaxAccumulateTree(size_t size, ValueType initialValue = LIMITS())
inline void updateFromChildren(NodeType &parent, const NodeType &left, const NodeType &right)
inline void pushDown(NodePosition parent)
inline void updateRange(size_t left, size_t right, IntegerType value)

Update min and max values in the range [left, right) with number value.

Parameters:

  • left – inclusive range left side

  • right – exclusive right side of range

  • value – number to be used for updating minimum and maximum

inline MinMax rangeMinMax(size_t l, size_t r)

Calculate minimum and maximum value in the range [l, r)

Parameters:

  • l – inclusive left side of range

  • r – exclusive right side of range

Returns:

std::pair {min, max}