HLD.H File Reference

Heavy-Light Decomposition for tree path queries on Aleph graphs. More...

#include <algorithm>
#include <cstddef>
#include <limits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_dynListStack.H>
#include <tpl_dynMapOhash.H>
#include <tpl_dynMapTree.H>
#include <tpl_graph.H>
#include <tpl_segment_tree.H>

Include dependency graph for HLD.H:

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

Go to the source code of this file.

Classes
class	Aleph::hld_detail::HLD_Tree_Data< GT, SA >
class	Aleph::Gen_HLD< GT, T, Op, SA >
	Heavy-Light Decomposition with segment tree for path/subtree queries. More...
struct	Aleph::HLD_Sum< GT, T, SA >
	HLD with path/subtree sum queries. More...
struct	Aleph::HLD_Max< GT, T, SA >
	HLD with path/subtree max queries. More...
struct	Aleph::HLD_Min< GT, T, SA >
	HLD with path/subtree min queries. More...

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

Detailed Description

Heavy-Light Decomposition for tree path queries on Aleph graphs.

Heavy-Light Decomposition (HLD) partitions a rooted tree into heavy chains such that any root-to-node path crosses at most \(O(\log n)\) chains. Combined with a segment tree, this yields efficient path queries and point updates.

Concept Visualization

     [0] (Root)          Heavy edges: 0-2, 2-5, 5-7
    /   \                Light edges: 0-1, 1-3, 1-4, 2-6, 5-8
  [1]   [2]
  / \   / \              path_query(3, 8) crosses O(log n) chains
[3] [4][5] [6]           subtree_query(2) covers contiguous segment
      / \
    [7] [8]

This header provides a generic HLD engine parameterised by the graph type, value type, and an associative binary operation:

<tt>Gen_HLD<GT, T, Op, SA></tt>

• Preprocessing: \(O(n \log n)\) time and space (segment tree build).
• Path query: \(O(\log^2 n)\) time.
• Subtree query: \(O(\log n)\) time.
• Point update: \(O(\log n)\) time.
• LCA query: \(O(\log n)\) time (free from chain walk).

Three convenience aliases are provided:

• HLD_Sum<GT, T, SA> — path/subtree sum queries.
• HLD_Max<GT, T, SA> — path/subtree max queries.
• HLD_Min<GT, T, SA> — path/subtree min queries.

Note

The binary operation Op must be associative and commutative for correct path queries. Non-commutative operations require directional accumulation (not currently supported).

Example: Path sum queries

using G = List_Graph<Graph_Node<int>, Graph_Arc<int>>;
G g;
// ... build a tree in g ...
auto node_val = [](G::Node * p) { return p->get_info(); };
HLD_Sum<G, int> hld(g, root, node_val);
 
int s = hld.path_query(u, v);     // sum on path u..v
hld.point_update(u, 42);          // set value of u to 42
int sub = hld.subtree_query(v);   // sum of subtree rooted at v

See also

tpl_segment_tree.H

LCA.H

tpl_graph.H

Author

Leandro Rabindranath León

Definition in file HLD.H.