Fenwick 알고리듬(2)

Binary Indexed Tree 구조 앞에서 살펴본 테이블로 표시된 Fenwick 을 왜 Binary Indexed Tree 구조라고 부르는지 살펴볼 시간이다. 여기서도 0번 index에 해당하는 원소는 큰 의미가 없다. 살펴볼 것은 각각의 푸른 색 원소들은 모두 마지막 노드에 속해있고, (바로 앞의 원소의 값과 자신의 값의 부분합을 가지고 있는) 녹색의 원소는 그 푸른색의 원소만을 자녀 노드로 구성하고 있다. 아래의 구조 내에서 처음 언급한 2개의 Operation이 어떻게 움직이는 지 다시 한번 살펴보자. 1) 부분 합을 가져와야 하는 경우 : Sum 만약 최초 배열의 0번부터 5번까지의 합을 가져와야 하는 경우라면, Fenwick 배열에서는 1번부터 6번까지의 배열 내의 값들의 합을 가져오면 된..

2020.09.14