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