SegmentTreeBase

template<class NodeTypeT, class FinalType>
class SegmentTreeBase

Not really a segment tree for storing segments as referred in academic literature. Can be considered a full, almost perfect, augmented binary tree. In the context of competitive programming often called segment tree.

Child classes are expected to implement updateFromChildren(NodeType&parent, NodeType& left, NodeType& right) method which calculates inner node values from children nodes.

Template Parameters:

  • NodeTypeT – type of each tree element

  • FinalType – final child class used for curiously recurring template pattern

Subclassed by LazySegmentTreeBase< std::pair< IntegerType, IntegerType >, std::pair< IntegerType, IntegerType >, MinMaxAccumulateTree< IntegerType > >, LazySegmentTreeBase< int, uint8_t, RangeAssignMaxTree >, PointSetSegmentTree< int, PointSetMinTree >

Public Types

using NodePosition = size_t
using NodeType = NodeTypeT

Public Functions

inline explicit SegmentTreeBase(size_t size)

Create tree with size leaves.

Parameters:

size – number of leaves in the tree

inline SegmentTreeBase(size_t size, const NodeType &initialValue)

Create a tree with given size and initial value.

Inner nodes are calculated from leaves.

Parameters:

  • size – number of leaves

  • initialValue – initial leave value