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

Public Types

using NodePosition = size_t
using NodeType = NodeTypeT

Public Functions

SegmentTreeBase(size_t size)

Create tree with size leaves.

Parameters

  • size: number of leaves in the tree

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