Skip to content

lcaBinaryLifting ​

lcaBinaryLifting(adj: usize[][], root: usize): Lca constrói tabelas de binary lifting 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 Lca retornada é um handle de propriedade do chamador de tyrus:algorithm; ela expõe query(u, v), que devolve o menor ancestral comum dos vértices u e v em O(log n) com binary lifting.

Construção ​

SintaxeDescrição
lcaBinaryLifting(adj: usize[][], root: usize)Construir tabelas de LCA sobre a árvore adj, enraizada em root

Métodos ​

MétodoAssinaturaRetornaDescrição
query(u: usize, v: usize)usizeMenor ancestral comum dos vértices u e v

Complexidade ​

OperaçãoComplexidade Temporal
construçãoO(n log n), tabelas de binary lifting
queryO(log n)
memóriaO(n log n)

Exemplos ​

árvore balanceada ​

tyrus
import { lcaBinaryLifting } from "tyrus:algorithm";

const adj: usize[][] = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2]];
const lca = lcaBinaryLifting(adj, 0);

print(lca.query(3, 4));  // 1
print(lca.query(5, 6));  // 2
print(lca.query(3, 6));  // 0

caminho profundo ​

tyrus
import { lcaBinaryLifting } 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 lca = lcaBinaryLifting(path, 0);

print(lca.query(9, 1));  // 1
print(lca.query(9, 8));  // 8
print(lca.query(0, 9));  // 0

único vértice ​

tyrus
import { lcaBinaryLifting } from "tyrus:algorithm";

const single: usize[][] = [[]];
const lca = lcaBinaryLifting(single, 0);

print(lca.query(0, 0));  // 0

importação por namespace ​

tyrus
import * as alg from "tyrus:algorithm";

const lca = alg.lcaBinaryLifting([[1], [0, 2], [1]], 0);
print(lca.query(1, 2));  // 1
print(lca.query(0, 2));  // 0