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}