펜윅 트리(1차원 펜윅 트리, Fenwick Tree, Binary Indexed Tree)
ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 위와 같은 1차원 배열이 있다. 해당 배열에서 ary[3]~ary[7] 구간합을 구하고자 한다. 가장 기본적인 코드는 아래와 같이 하나씩 모두 더하는 것이다. 해당 코드의 시간복잡도는 O(N) 이다.(연산의 수가 M일 경우 O(MN)) 펜윅트리를 사용하게 되면 이를 O(logN) 으로 감소시킬 수 있다. 그렇다면 펜윅트리가 무엇인지 알아보자. 1. 펜윅트리란 무엇인가? 펜윅트리는 Binary Indexed Tree, BIT 라고도 하며, 쉽게 말해 구간합을 빠르게 구하기 위한 자료구조이다. 2. 트리만들기(초기화) 입력받은 배열 ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 를 이용해 펜윅트리를 만들어 보자. 펜윅트..
