Aleph::Assign_Sum_Policy< T > Struct Template Reference

Range assign + range sum policy. More...

#include <tpl_segment_tree.H>

Public Types
using	value_type = T
using	lazy_type = std::pair< bool, T >

Static Public Member Functions
static constexpr T	combine (const T &a, const T &b) noexcept
static constexpr T	apply (const T &val, const lazy_type &lz, size_t count) noexcept
static constexpr lazy_type	compose (const lazy_type &old_lz, const lazy_type &new_lz) noexcept
static constexpr T	value_identity () noexcept
static constexpr lazy_type	lazy_identity () noexcept

Detailed Description

template<typename T>
struct Aleph::Assign_Sum_Policy< T >

Range assign + range sum policy.

Policy for Gen_Lazy_Segment_Tree implementing "range assign" + "range sum" updates/queries.

• combine(a, b) = a + b
• apply(val, (true, x), count) = x * count
• compose(old, new): new overrides old if new.first is true.

The lazy type is pair<bool, T> where first indicates whether an assignment is pending.

Template Parameters

T	arithmetic type.

Note

This policy is useful for classic tasks like "set a[l..r] = x" while querying range sums.

Definition at line 861 of file tpl_segment_tree.H.

Member Typedef Documentation

lazy_type

template<typename T >

using Aleph::Assign_Sum_Policy< T >::lazy_type = std::pair<bool, T>

Definition at line 864 of file tpl_segment_tree.H.

value_type

template<typename T >

using Aleph::Assign_Sum_Policy< T >::value_type = T

Definition at line 863 of file tpl_segment_tree.H.

Member Function Documentation

apply()

template<typename T >

static constexpr T Aleph::Assign_Sum_Policy< T >::apply ( const T &  val, const lazy_type &  lz, size_t  count  )

inlinestaticconstexprnoexcept

Definition at line 871 of file tpl_segment_tree.H.

References Aleph::count(), and Aleph::divide_and_conquer_partition_dp().

combine()

template<typename T >

static constexpr T Aleph::Assign_Sum_Policy< T >::combine ( const T &  a, const T &  b  )

inlinestaticconstexprnoexcept

Definition at line 866 of file tpl_segment_tree.H.

compose()

template<typename T >

static constexpr lazy_type Aleph::Assign_Sum_Policy< T >::compose ( const lazy_type &  old_lz, const lazy_type &  new_lz  )

inlinestaticconstexprnoexcept

Definition at line 877 of file tpl_segment_tree.H.

References Aleph::divide_and_conquer_partition_dp().

lazy_identity()

template<typename T >

static constexpr lazy_type Aleph::Assign_Sum_Policy< T >::lazy_identity ( )

inlinestaticconstexprnoexcept

Definition at line 885 of file tpl_segment_tree.H.

value_identity()

template<typename T >

static constexpr T Aleph::Assign_Sum_Policy< T >::value_identity ( )

inlinestaticconstexprnoexcept

Definition at line 883 of file tpl_segment_tree.H.

---

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

• tpl_segment_tree.H