백준 2042: 구간 합 구하기 (펜윅 트리 {Binary Index Tree} / with Python)

펜윅트리는 O(N)에 구할 연산을 O(logN)에 해결할 수 있게 해준다.

( 구간 합 구하기 ) 

펜윅트리는 "누적합"에 특화되어있는 자료구조이다. 

 

두 가지 연산만 잘 알아두면되는다.

1. update

2. prefix_sum이다. 

 

 

아래와 같은 도표를 보면 이해가 쉽다!

그림 출처 : https://www.acmicpc.net/blog/view/21