heavyLightDecomposition
heavyLightDecomposition(adj: usize[][], root: usize): Hld construye una descomposición heavy-light sobre el árbol no dirigido descrito por la lista de adyacencia adj, donde adj[v] guarda los vecinos del vértice v y root ancla cada consulta. La Hld devuelta es un handle de propiedad del llamador de tyrus:algorithm; expone queryPath(u, v), que devuelve los rangos contiguos [l, r] (en el orden de position) cuya unión cubre la ruta u → v del árbol en O(log n), listos para alimentar un segment tree para consultas de rutas.
Construcción
| Sintaxis | Descripción |
|---|---|
heavyLightDecomposition(adj: usize[][], root: usize) | Descomponer el árbol adj en cadenas pesadas, enraizado en root |
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
queryPath | (u: usize, v: usize) | [usize, usize][] | Rangos de cadena cuya unión cubre la ruta u → v |
position | (v: usize) | usize | Posición lineal por cadena del vértice v |
head | (v: usize) | usize | Vértice en la cima de la cadena pesada que contiene a v |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
| construcción | O(n), un DFS más la asignación de cadenas |
queryPath | O(log n), a lo sumo O(log n) rangos de cadena |
position, head | O(1) |
| memoria | O(n) |
Ejemplos
árbol balanceado
tyrus
import { heavyLightDecomposition } from "tyrus:algorithm";
const adj: usize[][] = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2]];
const hld = heavyLightDecomposition(adj, 0);
print(hld.queryPath(3, 4)); // [[3, 3], [1, 2]]
print(hld.queryPath(5, 4)); // [[4, 5], [3, 3], [0, 1]]
print(hld.position(3)); // 2
print(hld.head(3)); // 0camino profundo
tyrus
import { heavyLightDecomposition } from "tyrus:algorithm";
const path: usize[][] = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]];
const hld = heavyLightDecomposition(path, 0);
print(hld.queryPath(9, 1)); // [[1, 9]]
print(hld.queryPath(0, 9)); // [[0, 9]]único vértice
tyrus
import { heavyLightDecomposition } from "tyrus:algorithm";
const single: usize[][] = [[]];
const hld = heavyLightDecomposition(single, 0);
print(hld.queryPath(0, 0)); // [[0, 0]]importación por namespace
tyrus
import * as alg from "tyrus:algorithm";
const hld = alg.heavyLightDecomposition([[1], [0, 2], [1]], 0);
print(hld.queryPath(1, 2)); // [[1, 2]]