Lazy Segment Tree1 [2] Segment Tree (Lazy Propagation) Lazy-Segment Tree는 기본 세그먼트 트리에 구간에 대한 업데이트를 적용하는 쿼리에 적합한 자료구조이다. 기존 Segment Tree는 매 Update 쿼리마다 Tree의 Leaf node까지 가서 업데이트를 적용하지만 구간에 대해 업데이트가 필요한 경우엔, 그걸 일일이 다 바꿔주는 것이 비효율적이다. 해당 구간을 나중에 조회하지 않을 수도 있기 때문이다. 그럼 해당 구간을 언제 업데이트해줘야 하나? 물론 그 구간을 조회하거나 업데이트 해야 할 때 이다. 그때 아니면 굳이 밑으로 내려갈 필요가 없다. 해당 구간에 업데이트해야 할 값을 배열로 가지고 있고 (segtree와 동일한 배열) 해당 지점을 update 혹은 find로 접근할 때 propagation을 해준다. Propagation vo.. 2020. 9. 28. 이전 1 다음
