tpl_mo_algorithm.H File Reference

Mo's algorithm for offline range queries. More...

#include <algorithm>
#include <cmath>
#include <concepts>
#include <type_traits>
#include <utility>
#include <tpl_array.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynList.H>
#include <ah-errors.H>

Include dependency graph for tpl_mo_algorithm.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Mo_Query
	A query for Mo's algorithm: inclusive range [l, r] with id. More...
class	Aleph::Gen_Mo_Algorithm< T, Policy >
	Offline range query engine using Mo's algorithm. More...
struct	Aleph::Distinct_Count_Policy< T >
	Policy: count distinct elements in a range. More...
struct	Aleph::Powerful_Array_Policy< T >
	Policy: "powerful array" sum = sum(cnt[x]^2 * x). More...
struct	Aleph::Range_Mode_Policy< T >
	Policy: range mode (most frequent element). More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Concepts
concept	Aleph::MoPolicy
	Concept constraining a policy for Mo's algorithm.

Typedefs
template<typename T >
using	Aleph::Distinct_Count_Mo = Gen_Mo_Algorithm< T, Distinct_Count_Policy< T > >
	Mo's algorithm specialised for counting distinct elements.
template<typename T >
using	Aleph::Powerful_Array_Mo = Gen_Mo_Algorithm< T, Powerful_Array_Policy< T > >
	Mo's algorithm specialised for the "powerful array" query.
template<typename T >
using	Aleph::Range_Mode_Mo = Gen_Mo_Algorithm< T, Range_Mode_Policy< T > >
	Mo's algorithm specialised for range mode queries.

Detailed Description

Mo's algorithm for offline range queries.

Mo's algorithm answers Q offline range queries on a static array of N elements in O((N+Q)sqrt(N)) time. It is useful when the query function is "decomposable" (maintainable via add/remove of single elements) but has no algebraic structure (not a monoid, not invertible, not idempotent).

Classic applications: distinct element count, mode, powerful array.

The implementation uses the snake-optimized sweep (alternating direction of the right pointer in even/odd blocks) for better cache behaviour.

Complexity

Phase	Time	Space
Sort queries	O(Q lg Q)	O(Q)
Sweep	O((N+Q) sqrt(N))	O(N+Q)
Total	O((N+Q) sqrt(N))	O(N+Q)

Note

Mo's algorithm on trees is not covered here (it depends on the graph subsystem and will be a separate header).

See also

tpl_segment_tree.H Online range queries (monoid).

tpl_sparse_table.H Static O(1) range queries (idempotent).

tpl_fenwick_tree.H Prefix-based range queries (invertible).

Author

Leandro Rabindranath León

Definition in file tpl_mo_algorithm.H.