tpl_mo_on_trees.H File Reference

Mo's algorithm on trees: offline subtree and path queries. More...

#include <algorithm>
#include <cmath>
#include <concepts>
#include <vector>
#include <tpl_array.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynList.H>
#include <tpl_dynListStack.H>
#include <tpl_mo_algorithm.H>
#include <tpl_tree_node.H>
#include <ah-errors.H>

Include dependency graph for tpl_mo_on_trees.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Mo_On_Trees< GT, Policy >
	Offline subtree and path queries on trees via Mo's algorithm. More...
class	Aleph::Gen_Mo_On_Tree_Node< T, Policy >
	Offline subtree and path queries on N-ary trees (Tree_Node). More...

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

Concepts
concept	Aleph::MoTreeGraph
	Concept constraining a graph type usable for Mo on Trees.

Typedefs
template<class GT >
using	Aleph::Distinct_Count_Mo_On_Trees = Gen_Mo_On_Trees< GT, Distinct_Count_Policy< typename GT::Node::Node_Type > >
	Mo on Trees specialised for counting distinct node values.
template<class GT >
using	Aleph::Powerful_Array_Mo_On_Trees = Gen_Mo_On_Trees< GT, Powerful_Array_Policy< typename GT::Node::Node_Type > >
	Mo on Trees specialised for the "powerful array" query.
template<class GT >
using	Aleph::Range_Mode_Mo_On_Trees = Gen_Mo_On_Trees< GT, Range_Mode_Policy< typename GT::Node::Node_Type > >
	Mo on Trees specialised for range mode queries.
template<typename T >
using	Aleph::Distinct_Count_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Distinct_Count_Policy< T > >
	Mo on Tree_Node specialised for counting distinct values.
template<typename T >
using	Aleph::Powerful_Array_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Powerful_Array_Policy< T > >
	Mo on Tree_Node specialised for the "powerful array" query.
template<typename T >
using	Aleph::Range_Mode_Mo_On_Tree_Node = Gen_Mo_On_Tree_Node< T, Range_Mode_Policy< T > >
	Mo on Tree_Node specialised for range mode queries.

Detailed Description

Mo's algorithm on trees: offline subtree and path queries.

Extension of Mo's algorithm to tree structures. Given a rooted tree with N nodes and Q offline queries (either over subtrees or over paths), this class answers all queries in O((N+Q)√N) time by flattening the tree into an array via an Euler tour and then applying the classic Mo sweep.

Why Mo on Trees?

Many tree problems ask aggregate questions over subtrees or paths (e.g. "how many distinct species live in this subtree?" or "what is the most frequent label on the path from u to v?"). Naïve answers cost O(N) per query, giving O(NQ) total. Mo on Trees reduces this to O((N+Q)√N) — a substantial improvement when Q is large.

How it works

1. Euler-tour flattening – a DFS from the root assigns each node entry and exit timestamps. Subtrees become contiguous ranges in the entry-time order; paths become ranges in a double-occurrence tour combined with a toggle trick.
2. LCA via binary lifting – needed for path queries to correctly identify the range and handle the lowest common ancestor.
3. Mo sweep – queries are sorted into √N blocks and swept with a sliding window (snake-optimized), exactly as in Gen_Mo_Algorithm.

Complexity

Phase	Time	Space
Build (Euler + LCA)	O(N log N)	O(N log N)
Sort queries	O(Q lg Q)	O(Q)
Sweep (subtree)	O((N+Q) √N)	O(N+Q)
Sweep (path)	O((N+Q) √N)	O(N+Q)

Generic design

The class is templated on a graph type GT and a Policy. GT can be any Aleph-w graph: List_Graph, List_SGraph, or Array_Graph (and their digraph variants if the tree is stored as a directed graph). The tree topology is read but never modified; all auxiliary data is stored externally — zero performance impact on existing graph and tree structures.

The Policy must satisfy the same MoPolicy concept used by Gen_Mo_Algorithm (see tpl_mo_algorithm.H).

See also

tpl_mo_algorithm.H Mo's algorithm on arrays.

tpl_graph.H List_Graph.

tpl_sgraph.H List_SGraph.

tpl_agraph.H Array_Graph.

Author

Leandro Rabindranath León

Definition in file tpl_mo_on_trees.H.