Heavy-Light Decomposition과 세그먼트 트리를 활용한 트리 경로 최대 연속합 처리
문제 개요 및 핵심 접근법
트리 구조에서 두 정점 사이의 경로에 대해 최대 연속 부분합을 조회하고, 경로상의 모든 정점 값을 일괄 수정하는 연산을 처리해야 합니다. 정점의 개수와 쿼리의 개수가 최대 100,000에 달하므로, 단순한 순회 방식은 시간 제한을 초과합니다. 이를 효율적으로 해결하기 위해 Heavy-Light Decomposition(HLD)과 세그먼트 트리(Segment Tree)를 ...
10월 8일 04:22에 게시됨