펜윅 트리란? 펜윅 트리는 배열의 부분 합(prefix sum)을 계산할 때 사용되는 자료구조이다. 바이너리 인덱스 트리(Binary Indexed Tree, BIT) 또한 펜윅 트리를 지칭하는 용어이다. 펜윅 트리를 왜 써야 하는가? 앞에서 펜윅 트리가 부분 합을 계산할 때 사용된다고 했다. 정확히 말하자면 펜윅트리는 실시간으로 배열의 요소가 업데이트 되는 상황에서 부분합을 구할 때 사용된다. 예를 들어 [4, 5, 6, 7, 8, 9] 배열이 있고, 0번 인덱스부터 3번 인덱스까지 더한다면 4+5+6+7 = 22가 된다. 여기서 2번 인덱스를 6에서 10으로 변경한다고 하자. 그렇다면 앞서 0번 인덱스부터 3번 인덱스까지 더한 부분 합 22는 더 이상 쓸모없게 된다. 2번 인덱스가 6에서 10으로 바..