Heavy-Light Decomposition과 세그먼트 트리를 활용한 트리 경로 최대 연속합 처리
문제 개요 및 핵심 접근법
트리 구조에서 두 정점 사이의 경로에 대해 최대 연속 부분합을 조회하고, 경로상의 모든 정점 값을 일괄 수정하는 연산을 처리해야 합니다. 정점의 개수와 쿼리의 개수가 최대 100,000에 달하므로, 단순한 순회 방식은 시간 제한을 초과합니다. 이를 효율적으로 해결하기 위해 Heavy-Light Decomposition(HLD)과 세그먼트 트리(Segment Tree)를 ...
10월 8일 04:22에 게시됨
경로 및 서브트리 갱신을 위한 Heavy-Light Decomposition 활용
이 문제는 트리 위에서 두 가지 쿼리를 처리해야 하는 고전적인 HLD(Heavy-Light Decomposition) 적용 문제입니다. 노드 구간의 지연 갱신과 서브트리 합 질의를 효율적으로 해결해야 합니다.
핵심 개념
트리를 선형 구조로 변환하여 구간 자료구조를 적용하는 것이 핵심입니다. DFS 순서를 활용하면 서브트리를 연속된 구간으로 표현할 수 있으며, Heavy-Light Decomposi ...
8월 1일 09:05에 게시됨