펜윅 트리

펜윅 트리는 세그먼트 트리에서 조금 더 발전한 형태(?)인 것 같다.

세그먼트 트리에서 우측 노드를 잘라내어 좌측 노드들로만 구성되어 있고 비트 연산으로 부분합을 구할 수 있다.

위의 트리 속 노드를 가지고 계산할때 한 비트씩 차이를 주면 값을 알 수 있기 때문이다.

자세한건 직접 해보면 앎.

어디에 쓰이나?

- 부분합을 구할때 쓴다.

왜 쓰이나?

- n부터 k까지의 부분합을 구할 시, 하나하나 구하게 되면 시간 복잡도가 O(n)이 된다.

  그러나 트리를 이용하게 되면 O(logN) 형태가 된다. 큰 범위값을 구할때 적은 시간동안 해결하기 위함이다.