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

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