자료구조 & 알고리즘/자료구조6 [2] Segment Tree (Lazy Propagation) Lazy-Segment Tree는 기본 세그먼트 트리에 구간에 대한 업데이트를 적용하는 쿼리에 적합한 자료구조이다. 기존 Segment Tree는 매 Update 쿼리마다 Tree의 Leaf node까지 가서 업데이트를 적용하지만 구간에 대해 업데이트가 필요한 경우엔, 그걸 일일이 다 바꿔주는 것이 비효율적이다. 해당 구간을 나중에 조회하지 않을 수도 있기 때문이다. 그럼 해당 구간을 언제 업데이트해줘야 하나? 물론 그 구간을 조회하거나 업데이트 해야 할 때 이다. 그때 아니면 굳이 밑으로 내려갈 필요가 없다. 해당 구간에 업데이트해야 할 값을 배열로 가지고 있고 (segtree와 동일한 배열) 해당 지점을 update 혹은 find로 접근할 때 propagation을 해준다. Propagation vo.. 2020. 9. 28. [1] Segment Tree Segment Tree 는 다양한 유형의 문제를 빠르게 해결해주는 자료구조이다. 구간에 대한 정보를 구하는 경우, 단순히 정렬한 후 Prefix Sum 을 이용해서 구간합을 빠르게 구할 수 있지만 만약 개별 쿼리 도중 배열에서 특정 요소의 값이 변경되야 하는 경우엔 매번 다시 정렬을 해야 되어 비효율적이다. 이러한 경우, 구간에 대한 정보를 담는 Tree를 구성할 수 있는데, 이를 세그먼트 트리라고 한다. 세그먼트 트리는 기본적으로 Complete Binary Tree이고, 모든 Element에 대한 정보가 트리의 Leaf Node에 포함된다. 그리고 그 위 node들은, 자식 node를 포함하는 구간에 대한 정보를 담는 것이다. 간단하게, 세그멘트 트리를 이용해서 구간합을 구하는 코드의 예시를 보자. .. 2020. 9. 13. 이전 1 2 다음
