Offline range query engine using Mo's algorithm. More...

#include <tpl_mo_algorithm.H>

Public Types
using	Item_Type = T

using	answer_type = typename Policy::answer_type

Public Member Functions
	Gen_Mo_Algorithm (std::initializer_list< T > il, Policy p=Policy())
	Construct from an initializer list.

	Gen_Mo_Algorithm (const Array< T > &arr, Policy p=Policy())
	Construct from an Array<T>.

	Gen_Mo_Algorithm (Array< T > and arr, Policy p=Policy())
	Construct from an Array<T> (move).

	Gen_Mo_Algorithm (const DynList< T > &lst, Policy p=Policy())
	Construct from a DynList<T>.

	Gen_Mo_Algorithm (const Gen_Mo_Algorithm &)=default

	Gen_Mo_Algorithm (Gen_Mo_Algorithm &&) noexcept(std::is_nothrow_move_constructible_v< Array< T > > and std::is_nothrow_move_constructible_v< Policy >)=default

Gen_Mo_Algorithm &	operator= (const Gen_Mo_Algorithm &)=default

Gen_Mo_Algorithm &	operator= (Gen_Mo_Algorithm &&) noexcept(std::is_nothrow_move_assignable_v< Array< T > > and std::is_nothrow_move_assignable_v< Policy >)=default

constexpr size_t	size () const noexcept
	Number of elements in the data array.

constexpr bool	is_empty () const noexcept
	True if the data array is empty.

void	swap (Gen_Mo_Algorithm &other) noexcept(noexcept(std::swap(std::declval< Policy & >(), std::declval< Policy & >())))
	Swap with `other` in O(1).

Array< answer_type >	solve (const Array< std::pair< size_t, size_t > > &ranges) const
	Solve queries given as (l, r) pairs.

Array< answer_type >	solve (const std::initializer_list< std::pair< size_t, size_t > > il) const
	Solve queries given as (l, r) pairs (initializer list).

Array< answer_type >	solve (Array< Mo_Query > queries) const
	Core solver: answer all Mo_Query objects.

Private Attributes
Array< T >	data_

Policy	pol_

Detailed Description

template<typename T, class Policy>
requires MoPolicy<Policy, T>
class Aleph::Gen_Mo_Algorithm< T, Policy >

Offline range query engine using Mo's algorithm.

Given a static array of N elements and Q range queries [l, r], Gen_Mo_Algorithm answers all queries in O((N+Q) sqrt (N)) time by sorting queries into blocks and sweeping a sliding window.

The user supplies a Policy object that maintains per-window state (add/remove elements, compute the current answer).

Template Parameters

T	Element type stored in the array.
Policy	A type satisfying `MoPolicy<Policy, T>`.

Example: // Count distinct elements in ranges

Distinct_Count_Mo<int> mo = {1, 2, 1, 3, 2, 1};

auto ans = mo.solve({{0, 2}, {1, 4}, {0, 5}});

// ans(0) == 2, ans(1) == 3, ans(2) == 3

Aleph::Gen_Mo_Algorithm
Offline range query engine using Mo's algorithm.
Definition tpl_mo_algorithm.H:142

Aleph::Gen_Mo_Algorithm::solve
Array< answer_type > solve(const Array< std::pair< size_t, size_t > > &ranges) const
Solve queries given as (l, r) pairs.
Definition tpl_mo_algorithm.H:265

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Definition at line 141 of file tpl_mo_algorithm.H.

Member Typedef Documentation

◆ answer_type

template<typename T , class Policy >

using Aleph::Gen_Mo_Algorithm< T, Policy >::answer_type = typename Policy::answer_type

Definition at line 148 of file tpl_mo_algorithm.H.

◆ Item_Type

template<typename T , class Policy >

using Aleph::Gen_Mo_Algorithm< T, Policy >::Item_Type = T

Definition at line 147 of file tpl_mo_algorithm.H.

Constructor & Destructor Documentation

◆ Gen_Mo_Algorithm() [1/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm	(	std::initializer_list< T >	il,
		Policy	p = `Policy()`
	)

inline

Construct from an initializer list.

Parameters

il	Initializer list used to populate the internal array.
p	Policy object copied/moved into the solver.

Exceptions

std::bad_alloc	If internal storage allocation fails.
Any	exception thrown by `T` copy/move construction or by `Policy` move construction.

Note: Complexity: O(n) time and O(n) space, where n = il.size().

Definition at line 161 of file tpl_mo_algorithm.H.

◆ Gen_Mo_Algorithm() [2/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm	(	const Array< T > &	arr,
		Policy	p = `Policy()`
	)

inline

Construct from an Array<T>.

Parameters

arr	Source array copied into internal storage.
p	Policy object copied/moved into the solver.

Exceptions

std::bad_alloc	If internal storage allocation fails.
Any	exception thrown by `T` copy construction or by `Policy` move construction.

Note: Complexity: O(n) time and O(n) space, where n = arr.size().

Definition at line 176 of file tpl_mo_algorithm.H.

◆ Gen_Mo_Algorithm() [3/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm	(	Array< T > and	arr,
		Policy	p = `Policy()`
	)

inline

Construct from an Array<T> (move).

Parameters

arr	Source array moved into internal storage.
p	Policy object copied/moved into the solver.

Exceptions

Any	exception thrown by `Array<T>` move construction or by `Policy` move construction.

Note: Complexity: O(1) time and O(1) extra space (amortized move).; noexcept when both Array<T> and Policy are nothrow-movable.

Definition at line 191 of file tpl_mo_algorithm.H.

◆ Gen_Mo_Algorithm() [4/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm	(	const DynList< T > &	lst,
		Policy	p = `Policy()`
	)

inline

Construct from a DynList<T>.

Parameters

lst	Source list copied into internal contiguous storage.
p	Policy object copied/moved into the solver.

Exceptions

std::bad_alloc	If internal storage allocation fails.
Any	exception thrown by `T` copy construction or by `Policy` move construction.

Note: Complexity: O(n) time and O(n) space, where n = lst.size().

Definition at line 206 of file tpl_mo_algorithm.H.

References Aleph::Gen_Mo_Algorithm< T, Policy >::data_, and Aleph::divide_and_conquer_partition_dp().

◆ Gen_Mo_Algorithm() [5/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm ( const Gen_Mo_Algorithm< T, Policy > & )

default

◆ Gen_Mo_Algorithm() [6/6]

template<typename T , class Policy >

Aleph::Gen_Mo_Algorithm< T, Policy >::Gen_Mo_Algorithm ( Gen_Mo_Algorithm< T, Policy > && ) const

defaultnoexcept

Member Function Documentation

◆ is_empty()

template<typename T , class Policy >

constexpr bool Aleph::Gen_Mo_Algorithm< T, Policy >::is_empty ( ) const

inlineconstexprnoexcept

True if the data array is empty.

Definition at line 233 of file tpl_mo_algorithm.H.

References Aleph::Gen_Mo_Algorithm< T, Policy >::data_.

◆ operator=() [1/2]

template<typename T , class Policy >

Gen_Mo_Algorithm & Aleph::Gen_Mo_Algorithm< T, Policy >::operator= ( const Gen_Mo_Algorithm< T, Policy > & )

default

◆ operator=() [2/2]

template<typename T , class Policy >

Gen_Mo_Algorithm & Aleph::Gen_Mo_Algorithm< T, Policy >::operator= ( Gen_Mo_Algorithm< T, Policy > && )

defaultnoexcept

◆ size()

template<typename T , class Policy >

constexpr size_t Aleph::Gen_Mo_Algorithm< T, Policy >::size ( ) const

inlineconstexprnoexcept

Number of elements in the data array.

Definition at line 227 of file tpl_mo_algorithm.H.

References Aleph::Gen_Mo_Algorithm< T, Policy >::data_, and Aleph::Gen_Mo_Algorithm< T, Policy >::size().

Referenced by Aleph::Gen_Mo_Algorithm< T, Policy >::size().

◆ solve() [1/3]

template<typename T , class Policy >

Array< answer_type > Aleph::Gen_Mo_Algorithm< T, Policy >::solve ( Array< Mo_Query > queries ) const

inline

Core solver: answer all Mo_Query objects.

The queries are sorted by block (snake-optimized), swept with a sliding window, and the answers are returned in original order.

Parameters

queries Array of Mo_Query{l, r, id}.

Returns: Array<answer_type> indexed by original query id.

Exceptions

std::bad_alloc	If the answers array or policy-internal storage allocation fails.
std::out_of_range	If any query has `r >= size()`, `l > r`, or `id >= queries.size()`.
Any	exception thrown by `Policy::init`, `Policy::add`, `Policy::remove`, or `Policy::answer`.

Note

Complexity:

Validation: O(q)
Sorting: O(q log q)
Sweep: O((n + q) sqrt(n)) amortized pointer moves
Total: O(q log q + (n + q) sqrt(n))

Extra space: O(q) for sorted queries and answers.

Definition at line 317 of file tpl_mo_algorithm.H.

References ah_out_of_range_error_if, Aleph::Array< T >::create(), Aleph::Gen_Mo_Algorithm< T, Policy >::data_, Aleph::divide_and_conquer_partition_dp(), l, Aleph::Mo_Query::l, Aleph::Gen_Mo_Algorithm< T, Policy >::pol_, r, and Aleph::Mo_Query::r.

◆ solve() [2/3]

template<typename T , class Policy >

Array< answer_type > Aleph::Gen_Mo_Algorithm< T, Policy >::solve ( const Array< std::pair< size_t, size_t > > & ranges ) const

inline

Solve queries given as (l, r) pairs.

Convenience overload: assigns sequential ids 0, 1, 2, ...

Parameters

ranges Array of (l, r) closed ranges (0-based, inclusive).

Returns: Array<answer_type> indexed by original query order.

Exceptions

std::bad_alloc	If temporary query/answer arrays cannot be allocated.
std::out_of_range	If any query has `r >= size()`, `l > r`, or an invalid id (validated in core solve).
Any	exception thrown by `Policy::init`, `Policy::add`, `Policy::remove`, or `Policy::answer`.

Note

Complexity:

Conversion to Mo_Query: O(q)
Total including core solve: O(q log q + (n + q) sqrt(n))

Extra space: O(q) for converted queries and answers.

Definition at line 265 of file tpl_mo_algorithm.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Mo_Algorithm< T, Policy >::solve().

Referenced by Aleph::Gen_Mo_Algorithm< T, Policy >::solve(), Aleph::Gen_Mo_Algorithm< T, Policy >::solve(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ solve() [3/3]

template<typename T , class Policy >

Array< answer_type > Aleph::Gen_Mo_Algorithm< T, Policy >::solve ( const std::initializer_list< std::pair< size_t, size_t > > il ) const

inline

Solve queries given as (l, r) pairs (initializer list).

Parameters

il	Initializer list of `(l, r)` closed ranges.

Returns: Array<answer_type> indexed by original query order.

Exceptions

std::bad_alloc	If temporary ranges/query/answer arrays cannot be allocated.
std::out_of_range	Propagated from `solve(const Array<...>&)` when query bounds are invalid.
Any	exception propagated from the underlying policy.

Note

Complexity: