SegmentTreeBase¶
-
template<class
NodeTypeT
, classFinalType
>
classSegmentTreeBase
¶ 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 elementFinalType
: final child class used for curiously recurring template pattern
Public Functions
-
SegmentTreeBase
(size_t size)¶ Create tree with size leaves.
- Parameters
size
: number of leaves in the tree