Skip to content

heavyLightDecomposition ​

heavyLightDecomposition(adj: usize[][], root: usize): Hld constrói uma decomposição heavy-light sobre a árvore não direcionada descrita pela lista de adjacência adj, onde adj[v] guarda os vizinhos do vértice v e root ancora cada consulta. A Hld retornada é um handle de propriedade do chamador de tyrus:algorithm; ela expõe queryPath(u, v), que devolve os intervalos contíguos [l, r] (na ordem de position) cuja união cobre o caminho u → v na árvore em O(log n), prontos para alimentar um segment tree para consultas de caminho.

Construção ​

SintaxeDescrição
heavyLightDecomposition(adj: usize[][], root: usize)Decompor a árvore adj em cadeias pesadas, enraizada em root

Métodos ​

MétodoAssinaturaRetornaDescrição
queryPath(u: usize, v: usize)[usize, usize][]Intervalos de cadeia cuja união cobre o caminho u → v
position(v: usize)usizePosição linear por cadeia do vértice v
head(v: usize)usizeVértice no topo da cadeia pesada que contém v

Complexidade ​

OperaçãoComplexidade Temporal
construçãoO(n), uma DFS mais a atribuição de cadeias
queryPathO(log n), no máximo O(log n) intervalos de cadeia
position, headO(1)
memóriaO(n)

Exemplos ​

árvore balanceada ​

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));  // 0

caminho 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]]

importação 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]]