Lazy Propagation 이란? 기존 세그먼트 트리에서 i 에서 j 까지의 구간을 업데이트 하기 위해서는 수행시간은 O(NlogN)의 시간이 걸리게 된다. 이 구간 없데이트 시간을 단축 시키기 위한 알고리즘이 필요한데 이때 사용하는 알고리즘이 Lazy Propagation(게으르게 전파) 알고리즘이다. 이 알고리즘의 수행 속도는 O(logN) 이다. Lazy Propagation 동작 방법 배열 {1,2,3,4,5} 가 있는 구간합의 예를 살펴 봅니다. 세그먼트 트리 구현시 다음과 같은 트리가 생성 됩니다. 이때 0번지 부터 2번지까지에 3을 더해 준다고 하면 다음과 같이 계산이 됩니다. 파랑색 부분을 계산하면서 노랑색 부분은 (0~1) 위치는 2번, (0~2) 위치는 3번, (0~4) 위치는 3번..