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.
- tparam NodeTypeT
type of each tree element
- tparam FinalType
final child class used for curiously recurring template pattern
Subclassed by LazySegmentTreeBase< int, uint8_t, RangeAssignMaxTree >, PointSetSegmentTree< int, PointSetMinTree >
Public Functions
-
inline explicit SegmentTreeBase(size_t size)¶
Create tree with size leaves.
- Parameters
size – number of leaves in the tree