Crate heavy_light_decomposition 

Heavy-Light Decomposition (HLD).

Heavy-Light Decomposition splits a tree into “heavy” paths (chains of vertices where each parent has its largest subtree as its first child) and “light” edges (connecting chains). Once decomposed, any path from u to v can be split into O(log n) segments, each lying within a single chain. By storing per-chain data in a Fenwick tree or segment tree, you can answer path queries / updates in O(log² n) overall.

This crate ships the decomposition itself: it computes for each vertex its parent, depth, subtree size, the head of the chain it belongs to, and its position in the linearised chain order. You can then plug in any range-query data structure of your choice on top of that linearisation.

Example

use heavy_light_decomposition::Hld;

// Tree:
//      0
//      |
//      1
//     / \
//    2   3
//    |   |
//    4   5
let adj = vec![
    vec![1],
    vec![0, 2, 3],
    vec![1, 4],
    vec![1, 5],
    vec![2],
    vec![3],
];
let hld = Hld::new(&adj, 0);
assert_eq!(hld.parent[1], Some(0));
assert_eq!(hld.depth[4], 3);

Structs

Hld

Heavy-Light Decomposition over a rooted tree.