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