Minusi

앞서서 펜윅 트리에 대해서 소개한 적이 있습니다[링크]. 위 링크에서 세그먼트 트리와의 비교점 역시 쓰여있으므로, 차이점을 알고 싶으신 분들은 위 링크를 방문해 주시면 되겠습니다. 따라서 이 포스팅에서는 순수하게 세그먼트 트리에 대해서 설명하도록 하겠습니다. 세그먼트 트리 역시 부분합을 빠르게 찾을 수 있는 자료구조입니다. 위키피디아에서는 다음과 같이 정의하고 있습니다 : 통계 트리(statistic tree)라도고 하는 세그먼트 트리(Segment tree) 는 세그먼트나 간격에 대한 정보를 저장하는 트리 자료구조입니다. 주어진 지점에서 포함된 세그먼트들을 쿼리할 수 있습니다. 이론적으로 정적 구조체이며, 이 말은 한번 만들어지면 수정될 수 없음을 의미합니다. 유사한 데이터 구조로 간격 트리(inter..