A standard segment tree that supports O(log n) for point update and range query. The binary operation must be commutative. More...

#include <flow_segment_tree.h>

Public Types
using	value_type = T
using	reference = T&
using	const_reference = const T&
using	pointer = T*
using	const_pointer = const T*
using	iterator = T*
using	const_iterator = const T*
using	difference_type = std::ptrdiff_t
using	container_type = Vector<T, Allocator>
using	allocator_type = container_type::allocator_type

Public Member Functions
constexpr	SegmentTree () noexcept(noexcept(container_type()) &&noexcept(BinOp()))
constexpr	SegmentTree (const allocator_type &allocator) noexcept(noexcept(container_type(allocator)) &&noexcept(BinOp()))
constexpr	SegmentTree (const SegmentTree &)=default
constexpr	SegmentTree (const SegmentTree &rhs, const allocator_type &allocator)
constexpr	SegmentTree (SegmentTree &&)=default
constexpr	SegmentTree (SegmentTree &&rhs, const allocator_type &allocator) noexcept(noexcept(container_type(std::move(rhs.data_), allocator)) &&noexcept(BinOp(std::move(rhs.binOp_))))
template<std::forward_iterator It>
constexpr	SegmentTree (It first, It last, BinOp binOp={}, const allocator_type &allocator={})
	Iterator range constructor.
constexpr	SegmentTree (std::initializer_list< T > list, BinOp binOp={}, const allocator_type &allocator={})
	Initializer list constructor.
	~SegmentTree ()=default
allocator_type	get_allocator () const noexcept
constexpr std::size_t	size () const
	Return the number of input elements. This only counts the leaf node from the input.
constexpr bool	empty () const
	Check if the segmeent tree is empty.
constexpr void	setPoint (std::size_t i, const T &value)
	Set the new value at index i, then update the tree structure.
constexpr std::optional< T >	getRange (std::size_t first, std::size_t last) const
	Query the value from [first, last) after applying the binary operator adjacent-pair wise. If the range is empty, return std::nullopt.

Private Member Functions
constexpr void	buildParent ()

Static Private Member Functions
static constexpr bool	hasParent (std::size_t i) noexcept
static constexpr std::size_t	getParent (std::size_t i) noexcept
static constexpr std::size_t	getLeftChild (std::size_t i) noexcept
static constexpr std::size_t	getSibling (std::size_t i) noexcept
static constexpr bool	isLeftChild (std::size_t i) noexcept
static constexpr bool	isRightChild (std::size_t i) noexcept

Private Attributes
container_type	data_
BinOp	binOp_

Detailed Description

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>
class flow::SegmentTree< T, BinOp, Allocator >

A standard segment tree that supports O(log n) for point update and range query. The binary operation must be commutative.

Template Parameters

T
Allocator
BinOp

Definition at line 14 of file flow_segment_tree.h.

Member Typedef Documentation

◆ allocator_type

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::allocator_type = container_type::allocator_type

Definition at line 25 of file flow_segment_tree.h.

◆ const_iterator

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::const_iterator = const T*

Definition at line 22 of file flow_segment_tree.h.

◆ const_pointer

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::const_pointer = const T*

Definition at line 20 of file flow_segment_tree.h.

◆ const_reference

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::const_reference = const T&

Definition at line 18 of file flow_segment_tree.h.

◆ container_type

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::container_type = Vector<T, Allocator>

Definition at line 24 of file flow_segment_tree.h.

◆ difference_type

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::difference_type = std::ptrdiff_t

Definition at line 23 of file flow_segment_tree.h.

◆ iterator

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::iterator = T*

Definition at line 21 of file flow_segment_tree.h.

◆ pointer

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::pointer = T*

Definition at line 19 of file flow_segment_tree.h.

◆ reference

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::reference = T&

Definition at line 17 of file flow_segment_tree.h.

◆ value_type

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

using flow::SegmentTree< T, BinOp, Allocator >::value_type = T

Definition at line 16 of file flow_segment_tree.h.

Constructor & Destructor Documentation

◆ SegmentTree() [1/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree ( )

inlineconstexprnoexcept

Definition at line 32 of file flow_segment_tree.h.

34 : data_(), binOp_() {

35 }

flow::SegmentTree::data_

container_type data_

Definition flow_segment_tree.h:28

flow::SegmentTree::binOp_

BinOp binOp_

Definition flow_segment_tree.h:29

References binOp_, and data_.

Referenced by SegmentTree(), SegmentTree(), SegmentTree(), and SegmentTree().

◆ SegmentTree() [2/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree ( const allocator_type & allocator )

inlineexplicitconstexprnoexcept

Definition at line 37 of file flow_segment_tree.h.

39 : data_(allocator), binOp_(){

40 }

flow::SegmentTree

A standard segment tree that supports O(log n) for point update and range query. The binary operation...

Definition flow_segment_tree.h:14

References binOp_, and data_.

◆ SegmentTree() [3/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree ( const SegmentTree< T, BinOp, Allocator > & )

constexprdefault

References SegmentTree().

◆ SegmentTree() [4/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree	(	const SegmentTree< T, BinOp, Allocator > &	rhs,
		const allocator_type &	allocator )

inlineconstexpr

Definition at line 43 of file flow_segment_tree.h.

44 : data_(rhs.data_, allocator), binOp_(rhs.binOp_) {

45 }

References binOp_, data_, and SegmentTree().

◆ SegmentTree() [5/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree ( SegmentTree< T, BinOp, Allocator > && )

constexprdefault

References SegmentTree().

◆ SegmentTree() [6/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree	(	SegmentTree< T, BinOp, Allocator > &&	rhs,
		const allocator_type &	allocator )

inlineconstexprnoexcept

Definition at line 48 of file flow_segment_tree.h.

50 : data_(std::move(rhs.data_), allocator), binOp_(std::move(rhs.binOp_)) {

51 }

References binOp_, data_, and SegmentTree().

◆ SegmentTree() [7/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

template<std::forward_iterator It>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree	(	It	first,
		It	last,
		BinOp	binOp = {},
		const allocator_type &	allocator = {} )

inlineexplicitconstexpr

Iterator range constructor.

Parameters

first	Iterator to first element.
last	Iterator to one-past-last element.
binOp	Binary operator.
alloc	Allocator.

Definition at line 59 of file flow_segment_tree.h.

                                                                    {}, const allocator_type& allocator = {})
      : data_(std::distance(first, last) * 2, allocator), binOp_(std::move(binOp)) {
      std::copy(first, last, data_.begin() + size());
      buildParent();
    }

◆ SegmentTree() [8/8]

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::SegmentTree	(	std::initializer_list< T >	list,
		BinOp	binOp = {},
		const allocator_type &	allocator = {} )

inlineexplicitconstexpr

Initializer list constructor.

Parameters

list	Initializer list.
binOp	Binary operator.
alloc	Allocator.

Definition at line 69 of file flow_segment_tree.h.

                                                                              {}, const allocator_type& allocator = {})
      : SegmentTree(list.begin(), list.end(), std::move(binOp), allocator) {
    }

◆ ~SegmentTree()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

flow::SegmentTree< T, BinOp, Allocator >::~SegmentTree ( )

default

Member Function Documentation

◆ buildParent()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

void flow::SegmentTree< T, BinOp, Allocator >::buildParent ( )

inlineconstexprprivate

Definition at line 147 of file flow_segment_tree.h.

                                 {
      for (std::size_t i = size(); i-- > 1;) {
        std::size_t left = getLeftChild(i);
        std::size_t right = left + 1;
        data_[i] = binOp_(data_[left], data_[right]);
      }
    }

References binOp_, data_, getLeftChild(), and size().

◆ empty()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

bool flow::SegmentTree< T, BinOp, Allocator >::empty ( ) const

inlineconstexpr

Check if the segmeent tree is empty.

Returns: true if the segment tree is empty.

Definition at line 90 of file flow_segment_tree.h.

                                 {
      return data_.empty();
    }

References data_.

◆ get_allocator()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

allocator_type flow::SegmentTree< T, BinOp, Allocator >::get_allocator ( ) const

inlinenoexcept

Definition at line 76 of file flow_segment_tree.h.

                                                  {
      return data_.get_allocator();
    }

References data_.

◆ getLeftChild()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr std::size_t flow::SegmentTree< T, BinOp, Allocator >::getLeftChild ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 164 of file flow_segment_tree.h.

                                                                  {
      return i * 2;
    }

Referenced by buildParent().

◆ getParent()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr std::size_t flow::SegmentTree< T, BinOp, Allocator >::getParent ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 159 of file flow_segment_tree.h.

                                                               {
      assert(hasParent(i) && "calling parent on the root node");
      return i / 2;
    }

References hasParent().

Referenced by getRange(), and setPoint().

◆ getRange()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

std::optional< T > flow::SegmentTree< T, BinOp, Allocator >::getRange	(	std::size_t	first,
		std::size_t	last ) const

inlineconstexpr

Query the value from [first, last) after applying the binary operator adjacent-pair wise. If the range is empty, return std::nullopt.

Parameters

first	The begin index.
last	The end index.

Returns: The range value or std::nullopt.

Definition at line 113 of file flow_segment_tree.h.

                                                                             {
      assert(first <= last && "invalid range");
      std::size_t elementSize = size();
      first += elementSize;
      last += elementSize;
 
      std::optional<T> result{};
      for (; first < last;) {
        if (isRightChild(first)) {
          if (!result) {
            result = data_[first];
          } else {
            *result = binOp_(*result, data_[first]);
          }
          ++first;
        }
 
        if (isRightChild(last)) {
          --last;
          if (!result) {
            result = data_[last];
          } else {
            *result = binOp_(*result, data_[last]);
          }
        }
 
        first = getParent(first);
        last = getParent(last);
      }
 
      return result;
    }

References binOp_, data_, getParent(), isRightChild(), and size().

◆ getSibling()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr std::size_t flow::SegmentTree< T, BinOp, Allocator >::getSibling ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 168 of file flow_segment_tree.h.

                                                                {
      return i ^ 1;
    }

Referenced by setPoint().

◆ hasParent()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr bool flow::SegmentTree< T, BinOp, Allocator >::hasParent ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 155 of file flow_segment_tree.h.

                                                          {
      return i > 1;
    }

Referenced by getParent(), and setPoint().

◆ isLeftChild()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr bool flow::SegmentTree< T, BinOp, Allocator >::isLeftChild ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 172 of file flow_segment_tree.h.

                                                            {
      return (i % 2) == 0;
    }

Referenced by isRightChild().

◆ isRightChild()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

constexpr bool flow::SegmentTree< T, BinOp, Allocator >::isRightChild ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 176 of file flow_segment_tree.h.

                                                             {
      return !isLeftChild(i);
    }

References isLeftChild().

Referenced by getRange().

◆ setPoint()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

void flow::SegmentTree< T, BinOp, Allocator >::setPoint	(	std::size_t	i,
		const T &	value )

inlineconstexpr

Set the new value at index i, then update the tree structure.

Parameters

i	The index.
value	New value.

Definition at line 97 of file flow_segment_tree.h.

                                                         {
      i += size();
      data_[i] = value;
      while (hasParent(i)) {
        std::size_t parent = getParent(i);
        std::size_t sibling = getSibling(i);
        data_[parent] = binOp_(data_[i], data_[sibling]);
        i = parent;
      }
    }

References binOp_, data_, getParent(), getSibling(), hasParent(), and size().

◆ size()

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::SegmentTree< T, BinOp, Allocator >::size ( ) const

inlineconstexpr

Return the number of input elements. This only counts the leaf node from the input.

Returns: The number of elements.

Definition at line 84 of file flow_segment_tree.h.

                                     {
      return data_.size() / 2;
    }

References data_.

Referenced by buildParent(), getRange(), and setPoint().

Member Data Documentation

◆ binOp_

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

BinOp flow::SegmentTree< T, BinOp, Allocator >::binOp_

private

Definition at line 29 of file flow_segment_tree.h.

Referenced by buildParent(), getRange(), SegmentTree(), SegmentTree(), SegmentTree(), SegmentTree(), and setPoint().

◆ data_

template<typename T, typename BinOp, typename Allocator = PolymorphicAllocator<T>>

container_type flow::SegmentTree< T, BinOp, Allocator >::data_

private

Definition at line 28 of file flow_segment_tree.h.

Referenced by buildParent(), empty(), get_allocator(), getRange(), SegmentTree(), SegmentTree(), SegmentTree(), SegmentTree(), setPoint(), and size().

The documentation for this class was generated from the following file:

flow_segment_tree.h

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ container_type

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ SegmentTree() [1/8]

◆ SegmentTree() [2/8]

◆ SegmentTree() [3/8]

◆ SegmentTree() [4/8]

◆ SegmentTree() [5/8]

◆ SegmentTree() [6/8]

◆ SegmentTree() [7/8]

◆ SegmentTree() [8/8]

◆ ~SegmentTree()

Member Function Documentation

◆ buildParent()

◆ empty()

◆ get_allocator()

◆ getLeftChild()

◆ getParent()

◆ getRange()

◆ getSibling()

◆ hasParent()

◆ isLeftChild()

◆ isRightChild()

◆ setPoint()

◆ size()

Member Data Documentation

◆ binOp_

◆ data_