heavy_light_decomposition_example.cc File Reference

Story-driven demo of Heavy-Light Decomposition path/subtree queries. More...

#include <Tree_Decomposition.H>
#include <tpl_graph.H>
#include <array>
#include <cassert>
#include <format>
#include <iomanip>
#include <iostream>
#include <string>

Include dependency graph for heavy_light_decomposition_example.cc:

Go to the source code of this file.

Functions
int	main ()
	Executable example demonstrating heavy-light decomposition on a small tree.

Detailed Description

Story-driven demo of Heavy-Light Decomposition path/subtree queries.

Scenario: "The Aurora Power Grid"

Each node is a substation with a current maintenance cost. We need:

• sum on any transmission path (u, v)
• sum on complete service areas (subtrees)
• point updates when maintenance budgets change.

Definition in file heavy_light_decomposition_example.cc.

Function Documentation

main()

int main

(

)

Executable example demonstrating heavy-light decomposition on a small tree.

Builds a sample "Aurora Power Grid" tree with per-node maintenance costs, constructs an HLD-based query structure, and exercises path-sum and subtree-sum queries. Results are validated against brute-force computations via assertions. The program also performs point updates (increment and set), re-validates affected queries, prints node mappings, query results, and shows how a path is split into base-array segments by the HLD.

Returns

int Returns 0 on successful completion (all assertions passed).

Definition at line 133 of file heavy_light_decomposition_example.cc.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, and r.