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 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