Algorithm1 [알고리즘] Segment Tree, lazy propagation 1. Segment Tree 세그먼트 트리는 트리 형태의 데이터를 활용해 어떤 구간에 대한 정보를 활용하는 데 사용한다. 아직 블로그 글에서 세그먼트 트리를 다루지 않았지만, 후에 다루어 볼 것이고, 먼저 lazy propagtion의 적용을 이 글에서 다루어 볼 것이다. 2. lazy propagation 느린 전파라고도 말하지만, 게으른 전파가 알고리즘을 더 잘 나타낼 수 있는 단어라고 생각하여 게으른 전파라 부르겠다. 세그먼트 트리에서 게으른 전파는 값을 갱신할 때 특정 값이 아니라 범위의 값을 변경할 때 사용한다. 세그먼트 트리는 log(N)으로 가능하지만, 범위의 값을 경신하기 위해 Nlog(N)의 연산이 필요하게 된다. 그래서 갱신을 트리의 모든 값에 항상 적용하는 게 아니라 필요할 때만 하는.. 2022. 8. 19. 이전 1 다음