Minusi

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