Minusi

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

펜윅 트리는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 위키피디아에서는 다음과 같이 정의하고 있습니다 : 펜윅 트리 또는 바이너리 인덱스드 트리 는 효과적으로 요소를 업데이트하고 수 배열의 구간합을 계산할 수 있는 자료구조입니다. 1989년 Boris Ryabko에 의해 처음 제안되었으며 1992년 추가로 수정되었습니다. 펜윅 트리는 Peter Fenwick에서 이름이 유래하였습니다. 일반 배열과 비교했을 때 구간 합에 대해 배열은 선형 시간이 필요하며, 이는 배열 요소를 업데이트하는 데에도 똑같이 적용됩니다. 펜윅 트리는 두 가지 작업 모두에 대해 O(log n) 시간에 수행할 수 있습니다. 이러한 자료구조 필요한 이유는 다음 상황들에 대해 효율적으로 처리할 수 ..