세그먼트 트리
-
🌲 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하라는 작업이 들어오면..
-
🌲 Segment Tree 1 - Segment Tree란?ALicademy 👩🏫👨🏫/알고리즘 2020. 8. 31. 16:33
원본은 링크를 통해 확인하실 수 있습니다 😃 Intro 🚀 스마트폰을 켜서 SNS를 들어가봅시다. 지난 한 달 동안 여러분이 받은 좋아요👍 의 합을 구하고 싶으면 어떻게 하면 될까요? 아마 여러분이 저와 비슷하다면 가장 먼저 '모든 게시물 중 지난 한 달 동안의 게시물에서 받은 좋아요 수를 일일이 더하면 되지 않을까요?' 라고 말씀하실지도 모릅니다. 이 방법을 사용했을 때 게시물의 수가 개이고 특정 기간 동안 받은 좋아요 수의 합을 묻는 query를 개 처리해야 한다면 시간 복잡도는 입니다. 이 방법도 나쁘지 않지만 더 효율적인 방법은 없을까요? 그래서 오늘 우리가 배울 것은 바로 구간의 합/ 차/ 최대값/ 최소값 등을 효율적으로 구하기 위해 쓰이는 자료 구조인 🌴Segment T..