ITPE * JackerLab

개요Link-Cut Tree는 동적으로 연결되거나 분리되는 트리 구조에서 효율적으로 경로 질의 및 갱신 연산을 수행할 수 있도록 설계된 고급 트리 기반 자료구조입니다. Sleator와 Tarjan에 의해 1983년 제안된 이 자료구조는 splay tree를 기반으로 하며, 각 노드의 서브트리나 루트까지의 경로에 대해 로그 시간 내 연산을 지원합니다. Union-Find, Euler Tour Tree보다 더 복잡한 트리 동작이 필요한 알고리즘에 적합합니다.1. 개념 및 정의 항목 설명 정의Link-Cut Tree는 포레스트(트리들의 집합) 구조에 대해 노드 간 연결(Link), 분리(Cut), 경로 질의(Query), 경로 갱신(Update)을 동적으로 처리하는 트리 자료구조입니다.목적트리 구조가 변동하..

개요Heavy-Light Decomposition(HLD)은 트리 구조에서 경로 쿼리(Query)나 업데이트(Update)를 빠르게 처리하기 위해 고안된 분할 기법입니다. 트리의 간선을 무거운(Heavy) 간선과 가벼운(Light) 간선으로 분류하여, 경로를 소수의 구간(segment)으로 분해하고, 각 구간에 대해 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree) 같은 자료구조를 적용하여 O(log² n) 또는 O(log n) 시간 복잡도로 효율적인 처리를 가능하게 합니다.1. 개념 및 정의 항목 내용 정의트리를 Heavy 간선과 Light 간선으로 분할하여 경로 쿼리와 업데이트를 최적화하는 알고리즘적 테크닉목적트리 경로 질의의 시간 복잡도를 개선하여 고속 연산 지원필요성단..