목록2026/03/07 (1)
Elevation
트리 (3) - 느리게 갱신되는 세그먼트 트리(lazy propagation)
세그먼트 트리는 구간 쿼리에 특화되어 있어, 주어진 $[L, R]$ 구간의 합이나 최댓값/최솟값을 구하는 문제를 $O(\log N)$만에 잘 처리해 준다. 문제는 업데이트가 점 단위가 아닌 구간으로 주어지는 경우에 발생한다. 한 번의 점 단위 업데이트를 진행할 때 $O(\log N)$이 소요되므로, 일일이 구간 내 모든 값을 업데이트하는 것은 비효율적이다. 느리게 갱신되는 세그먼트 트리는 구간에 대한 정보를 담고 있는 세그먼트 트리의 구조를 십분 활용하여 구간 단위 업데이트를 $O(\log N)$만에 수행한다. lazy propagation의 원리기본 세그먼트 트리의 아이디어는 구간 쿼리를 처리할 때 구간 내에 포함되는 노드 밑으로는 더 이상 내려가지 않고 바로 결과를 반환하는 것이었다. 마찬가지로 l..
ps/tree
2026. 3. 7. 21:44