segment treee
-
🌲 Segment Tree 2 - 더 빠른 update를 위한 Lazy Propagation!ALicademy 👩🏫👨🏫/알고리즘 2020. 9. 1. 19:27
원본은 링크를 통해 확인하실 수 있습니다. Intro 🚀 이전 글 마지막에 말씀드렸듯이 segment tree에서 특정 구간을 update할 때 leaf node를 일일이 방문해서 update하면 중복해서 방문하는 노드가 생깁니다. 이 때문에 정말 많은 update 연산을 해야 하는 경우 시간이 오래 걸릴 수 있습니다. 그래서 오늘은 더 빠른 udpate를 위한 기법인 Lazy propagation😴 에 대해 배워 보겠습니다! Lazy Propagation 😴 지금부터 여러분이 노드를 직접 update하는 일꾼👷♀️👷이라고 생각해봅시다! 여러분은 아래 예제와 같은 segment tree를 돌아다니면서 노드를 udpate합니다. 만약 arr의 0번째부터 2번째 인덱스까지 update하라는 작업이 들어오면..