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:

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