Fenwick Tree (1) 썸네일형 리스트형 159. Fenwick Tree 세그먼트 트리의 변형 버전인 펜윅 트리(Fenwick Tree)에 대해 알아본다. 펜윅 트리는 세그먼트 트리의 구조를 응용하여 원소들의 값이 변할 수 있을 때 누적합을 빠르게 구할 수 있게 하는 자료 구조이다. 먼저 합 세그먼트 트리에서 누적합을 구할 때 어떤 노드들이 사용되는지 확인해 보자. 합 세그먼트 트리를 설명할 때 노드들에 위와 같이 번호를 매기는 것이 일반적이라고 했다. 여기서 앞쪽 $k$개 원소의 누적합을 구할 때 합에 포함되는 노드들의 번호를 나열하면 다음과 같다. $k=1$인 경우: $8$ $k=2$인 경우: $4$ $k=3$인 경우: $4$, $10$ $k=4$인 경우: $2$ $k=5$인 경우: $2$, $12$ $k=6$인 경우: $2$, $6$ $k=7$인 경우: $2$, $6$,.. 이전 1 다음
