[ 펜윅트리(FenwickTree) ] 개념과 구현방법 (C++)

이번 글에서는 펜윅트리(FenwickTree) 에 대해서 이야기해보자.

이 글을 읽기 전에 먼저 '세그먼트 트리'에 대한 글을 읽고 오는 것을 권장한다.

세그먼트 트리를 모른다고 해서 펜윅트리를 절대 이해할 수 없다고 말을 할 수는 없지만, 펜윅트리라는 것이

세그먼트 트리에서 한 단계 더 응용된 자료구조로써, 더 간단하고 더 적은 메모리로 주어진 연산을 처리할 수 있도록

만들어 놓은 것이기 때문에 세그먼트 트리에 대해서 먼저 이해한 후에 펜윅트리를 알면 더 수월할 것 같다.

또한, 이 글에서도 세그먼트 트리와 비교를 하거나 비슷한 설명을 하면서 세그먼트 트리에 대한 이야기가 많이 나올 수 있는데,

세그먼트 트리에 대해서 알고 있다는 가정하에 진행하겠다. 아래의 링크는 '세그먼트 트리'에 대한 설명 글이다.

[ 세그먼트 트리 알아보기(Click) ]

1. 펜윅트리 (Fenwick Tree) ??

가장 먼저, 펜윅트리에 대해서 알아보자. 펜윅트리는 세그먼트 트리와 마찬가지로 '구간에 대한 연산'을 빠르게 진행하기

위해서 구현된 자료구조이다. 세그먼트 트리에 비해서 메모리 소모량이 적기도 하고, 세그먼트 트리를 구현하는 거에 비해서 코드 또한 굉장히 간단하기 때문에 세그먼트 트리에서 한 단계 응용된 자료구조라고 볼 수 있다.

펜윅트리의 전체적인 형태에 대해서 결과부터 보고 더 많은 과정을 알아보도록 하자.

크기가 8인 배열에 대한 세그먼트 트리는 다음과 같은 형태로 이루어져 있었다. (1번 Index부터 8번 Index를 사용했다고 가정)

각 동그라미는 노드를 의미하고, 노드 안에 숫자는 '배열의 인덱스 번호'를  나타낸 것이다.

빨강색 숫자들은 세그먼트 트리의 인덱스 번호를 표현해 놓은 것이다. 이런식으로, 부모와 노드가 구간과 구간의 연산으로

이루어져 있는 형태였으며, 리프노드는 배열의 값 그 자체를 가지고 있었다.

크기가 8인 배열에 대한 펜윅트리는 다음과 같은 형태로 존재한다.

정말 뜬금없는 그림이 나왔다. 사실 펜윅트리는 지금부터 차차 알아가겠지만, 트리의 형태보다는 위의 그림과 같은 형태로

이해하는 것이 더 수월하다고 생각한다. 가장 위에 '배열의 Index' 라고 적힌 숫자가 적혀있는 사각형들을 제외한

나머지 사각형들은 모두 펜윅트리에 들어가 있는 값을 의미한다. 옆에 빨간색 숫자는 펜윅트리의 인덱스 번호를 의미한다.

가장 눈에 띄는 특징 몇가지만 간략하게 적어보고 넘어가자면, 홀수번 Index들은 배열의 값을 그대로 저장하고 있다,

펜윅트리에 비해서 구간에 대한 연산을 저장하는 노드의 수가 줄어든 것 같다.. 뭐 이정도면 알고 넘어가자.

2. 펜윅트리 생성과정

세그먼트 트리는 그 크기를 설정하는 것 만으로도 엄청난 연산(?)이 필요했었다. 하지만 펜윅트리는 그렇지 않다.

펜윅트리는 배열의 크기만큼으로만 딱 설정을 해주면 된다. 즉, 크기가 N인 배열이 있다면, 펜윅트리의 크기 또한 N이 된다.

세그먼트 트리와 마찬가지로 펜윅트리 또한 '1번 Index'부터 사용한다. 0번 Index를 사용하지 않는다.

세그먼트 트리때는 부모와 노드의 관계를 Index번호로 간편하게 계산을 하기 위해서 0번 Index를 사용하지 않았지만,

펜윅트리는 '비트 연산'을 위해서 0번 Index를 사용하지 않는다. 펜윅트리의 코드가 굉장히 간단한 이유가 여기에 있다.

바로 '비트'를 가지고 연산을 진행하기 때문에 코드가 굉장히 간편하다. 특히, 0과 1로 이루어진 비트에서, '1'의 위치를

가지고 연산을 진행하게 된다. 즉 ! 펜윅트리를 구현해야 하는 우리는 '1'이 중요하기 때문에 '1'이 시작하는 숫자였으면

좋겠다는 것이다. 따라서, 0을 이진수로 나타낸 000000(2) 보다는, 0000001(2) 을 시작점으로 삼는 것이 연산에 있어서

편하기 때문에 '1번 Index'부터 사용을 하게 된다. 아직 무슨말인지 정확하게 몰라도 상관이 없다.

펜윅트리는 세그먼트 트리와는 달리 "누적합"에 대한 개념(0 ~ k번 Index까지의 합)을 많이 이용한다.

세그먼트 트리는 '누적합'보다는 '구간합'에 중점적으로 구현되어 있었지만, 펜윅트리는 '누적합'에 대한 개념을 이용한다.

위의 그림보다 조금 더 복잡한 그림을 가져와서 한번 이해해보도록 하자.

16칸 짜리에 대한 펜윅트리를 가져온 형태이다. 빨강색 글씨는 펜윅트리의 Index번호를 의미한다.

특징을 찾기에는 다소 어려운 그림이지만, 한번 찾아보도록 노력해보자.

일단 "홀수번 Index는 배열의 값을 그대로 갖는다." 라는 것은 쉽게 파악할 수 있다. 문제는 짝수번 Index이다.

어떤 짝수는, 1번 Index부터의 누적합을 가지고 있기도 하고, 어떤 Index는 2개의 Index에 대한 구간합만 가지고 있기도 하고,

어떤 짝수는, 4개의 Index에 대한 구간합만을 가지고 있기도 하다. 이제부터 "펜윅트리의 진가"가 나오게 된다.

처음에 잠깐 말했었는데, 펜윅트리는 '비트'를 이용해서 연산을 진행한다고 했다. 그럼 위의 인덱스들을 모두 2진수로 한번

적어보자.

각 Index번호들을 2진수로 나타낸 것이다. 여기서 하나만 더 알고 넘어가자. 펜윅트리는 '비트'를 이용해서 연산을 진행하는데,

그 중에서도 '1이 존재하는 최하위 비트 값'을 이용해서 연산을 진행한다. 그럼 '1이 존재하는 최하위 비트 값'을 한번

적어보자. 예를 들어서 2는 0010(2) 인데, 이 때 가장 오른쪽에 있는 '1'은 숫자 '2'를 의미한다.

3은 0011(2) 인데, 가장 오른쪽에 있는 '1'은 숫자 '1'을 의미한다.

8은 1000(2) 인데, 가장 오른쪽에 있는 '1'은 숫자 '8'을 의미한다. 이런식으로 매칭되는 숫자를 한번 다 적어보자.

위에서 말한 값들을 한번 모두 적어보았다. 그럼 저 숫자들의 의미를 위의 그림과 함께 비교해서보면서 파악해보자.

홀수번 Index들을 보면, 공통적으로 모두 '1'이라는 값을 갖는다. 즉, 홀수를 2진수로 나타내었을 때, 최하위 1비트 에는

무조건 '1'이 있다는 것이다. 그런데, 홀수번 Index들은 해당 자기자신의 값 '1개'에 대한 구간연산 결과값을 갖는다.

짝수번 Index를 보면 값이 가지각색이다. 그런데 ! 잘 보면 "해당 숫자들 만큼 앞으로 x칸 까지의 구간연산 결과값"을

갖는다는 것을 알 수 있다.

숫자 '2'는 0010(2) 이고, '1이 존재하는 최하위 비트' 는 '2'이고, 2번 Index는 2번부터 앞으로 2칸까지의 구간연산 결과값인

1번 Index + 2번 Index를 한 결과값을 가지고 있다.

숫자 '4'는 0100(2) 이고, '1이 존재하는 최하위 비트'는 '4'이고, 4번 Index는 4번부터 앞으로 4칸까지의 구간연산 결과값인

Arr[1] + Arr[2] + Arr[3] + Arr[4] 를 한 결과값을 가지고 있다.

숫자 '12'는 1100(2) 이고, '1이 존재하는 최하위 비트'는 '4'이고, 12번 Index는 12번부터 앞으로 4칸까지의 구간연산 결과값인

Arr[9] + Arr[10] + Arr[11] + Arr[12] 를 한 결과값을 가지고 있다.

이게 펜윅트리가 생성되는 과정이다. 홀수들은 무작정 "배열의 값을 그대로 갖는다 !" 라고 표현해도 절대 틀린 말은 아니지만,

보다 정확하게 말하자면, "홀수번 Index들을 2진수로 표현했을 때, '1이 존재하는 가장 최하위 비트 값' 은 항상'1'이 나오게 되고,

따라서, 현재 Index에서 1칸 앞 까지의 구간연산 결과값을 가지고 있습니다." 라고 표현할 수 있다.

정리해보자.

1. 펜윅트리는 비트를 이용해서 생성하게 된다.

2. 각 Index를 2진수로 표현했을 때, '1'이 존재하는 가장 최하위 비트의 값을 찾는다. = x

3. 해당 Index부터 x칸 앞까지의 구간연산에 대한 결과값을 갖는다.

펜윅트리는 1번 Index부터의 총 합인 '누적합'에 대한 개념이 이용된다고 말했는데, 이게 왜냐하면, '2', '4', '8', '16'과 같이

2의 거듭제곱꼴로 나타내는 Index번호들에 대해서는 1번 Index부터의 모든 합을 가지고 있기 때문이다.

생성과정에 대한 소스코드는 아래에서 따로 알아보도록 하자. 왜냐하면 Update를 하는 부분과 생성하는 부분이 동일하기 때문에

세그먼트 트리처럼 따로 생성해야 할 필요는 없기 때문이다.

3. 펜윅트리 구현방법

위에서 말한 펜윅트리에 대한 기본적인 설명과 어떻게 만들어지는 놈이지 파악하는 것만으로도 꽤 난이도가 있는 자료구조라는

느낌이 들 것이다. 그런데 문제는 지금부터 이걸 구현을 해야한다... 어떤 Index는 배열 원본의 값을 그대로 가지고.. 어떤 Index는

2개의 구간에 대한 Index만 가지고.. 어떤 Index는 4개의 구간에 대한 Index를 가지고.. 이를 파악하려면 2진수로 나타내서 최하위

1비트를 찾아야되고... 생각만으로도 굉장히 어려운 작업일 것 같지만 ! '비트연산'이라는 단순하면서도 너무나도 신기한 방법으로

간단하게 해결할 수가 있다. 위에서도 말했듯이, 생성을 하면서 업데이트하는 과정(특정 Index의 값을 변경하는 연산)부터

알아보자. 위의 그림을 다시한번 보자.

지금 초기에 펜윅트리에는 아무것도 없는 상태라고 가정하자. 모든 인덱스들이 '0'으로 초기화가 되어있고 N만큼의 공간만

할당되어 있는 상태이다. 그리고 배열은 총 16칸짜리 배열을 펜윅트리로 만들 것이고, 16칸 짜리 배열은 { 1, 2, 3, ..., 16 } 으로

순차적으로 정렬된 상태라고 가정하겠다. 이 배열을 Arr[] 배열이라고 표현하겠다. ( Arr[] = 원본 배열 )

그럼 가장 먼저 ! Arr[1] = 1 의 값을 펜윅트리에 넣는 과정을 알아보자.

먼저 보기 쉽게, 위의 그림에서 Arr[1]에 의해서 영향을 미치게 되는 노드들을 색깔로 칠해보겠다. 아마 다음과 같을 것이다.

위에서 말한 Arr[1] 의 값이 생성됨에 따라 값에 변화가 생기는 펜윅트리의 인덱스들에 색깔을 칠해본 것이다.

색칠된 인덱스들은 모두 공통적으로 "해당 인덱스가 갖는 결과값에 Arr[1]이 영향을 미치게 된다".

그럼 펜윅트리의 인덱스 번호들로만 본다면(빨간색 글씨) 1, 2, 4, 8, 16 번 Index가 Arr[1]에 의해서 영향을 미친다는 것을

알 수 있다. 이 '영향을 미치는 노드들'을 어떻게 찾아내는지 지금부터 알아보자.

계속해서 말하고 있지만, '비트'를 이용한다면 위의 노드들을 정말 손쉽게 찾아낼 수 있다.

그럼 영향을 미치는 Index번호들을(1, 2, 4, 8, 16) 비트로 표현하기 위해서 2진수로 적어보겠다.

1 = 0001(2)

2 = 0010(2)

4 = 0100(2)

8 = 1000(2)

16 = 10000(2)

무슨 규칙이 있을까 ?? 정확하게는 모르겠지만 '1로 표현된 비트가, 한 칸씩 앞으로 오는 것 같다' 라는 것 정도는 알 수 있을

것이다. 정답을 말하자면 "현재 Index에서 '1'이 있는 최하위 비트를 찾아서 '1'을 더해주는 연산" 을 하는 것이다.

확인해보자. 현재 Index = '1'번 Index이다(Arr[1]의 값을 설정하고 있으므로)

그럼 1 = 0001(2) 에서 '1'로 표현된 최하위 비트를 찾아보면, '1'이다. 해당 비트에 '1'을 더해보자.

즉, 0001 + 1 이 되는 것이다. 계산해보면, 0010(2) 가 나오게 된다. 계속 진행해보자.

0010(2) 에서 '1'이 있는 최하위 비트를 찾아보면 빨강색으로 표시된 '1'이고, 해당 비트에 '1'을 더해보자.

0010(2)

+  1

ㅡㅡㅡㅡ

0100(2)  가 된다. 반복해서 진행해보면 다음과 같이 숫자가 변하는 것을 알 수 있다.

0001 → 0010 → 0100 → 1000 → 10000 이런식으로 진행된다는 것을 알 수 있다.

즉, "현재 Index에서부터, 펜윅트리의 크기가 넘지 않을 때 까지 계산을 진행하는데, 그 계산은 '1이 존재하는 최하위 비트를

찾아서, 해당 비트에 '1'을 더하는 연산을 진행" 하면, 해당 Index에 의해서 영향을 끼치는 펜윅트리의 인덱스들을 찾을 수

있게 된다.

한 개만 더해보자. Arr[9] (9) 에 값을 넣는다고 생각해보자. 배열의 '9번 Index'에 의해서 영향을 미치는 펜윅트리의 인덱스들을

색깔을 칠해보면 다음과 같다.

위에서 색칠한 인덱스들이 '9번 Index' 에 의해서 영향을 미치게 되는 인덱스 들이다.

색칠한 인덱스들을 나열해보면 { 9 , 10 , 12 , 16 } 이다. 위와 같은 계산을 진행해보자.

9 = 1001(2) , 10 = 1010(2) , 12 = 1100(2) , 16 = 10000(2) 이다.

1001(2) 에서 '1'이 존재하는 최하위 비트는 빨강색으로 표시된 비트이고, 해당 비트에 1을 더해보자.

1001

+    1

ㅡㅡㅡ

1010(2)   이 된다. 정말 신기하게도 9번 Index 다음에 영향을 미치는 Index 번호는 10번 Index이고, 10을 2진수로 표현하면

1010(2) 이 된다. 한번 더 진행해보자. 1010(2) 에서 '1'이 존재하는 최하위 비트는 빨강색으로 표시된 비트이고, 해당 비트에

1을 더해보자.

1010

+  1

ㅡㅡㅡ

1100(2) 이 된다. 10번 Index 다음에는 12번 Index가 영향을 미치게 되는데, 12를 2진수로 표현하면 1100(2)가 된다.

1100(2) 에서 '1'이 존재하는 최하위 비트는 빨강색으로 표시된 비트이고, 해당 비트에 1을 더해보자.

1100(2)

+1

ㅡㅡㅡㅡ

10000(2) 이 된다. 12번 Index 다음으로 영향을 미치는 Index는 16번 Index이고 16을 2진수로 표현하면 10000(2)가 된다.

이렇게 ! 우리는 "현재 Index번호에서 '1'이 존재하는 최하위 비트만 찾아서 해당 비트에 '1'을 더해주는 연산을 반복" 해주면

해당 Index에 의해서 영향을 미치는 모든 Index들을 찾을 수 있게 된다.

그런데 문제는 ! " '1'이 존재하는 최하위 비트를 찾는 과정 " 이 문제이다. 모든 숫자들을 2진수로 다 나타내서 반복문을 통해서

1을 찾을 수도 있겠지만, 이런 귀찮은 과정을 하지 않아도 된다. 바로 & 연산을 이용해서 간편하게 계산할 수 있다.

결론부터 적어보면 [ Index번호 = Index번호 + (Index번호 & -Index번호) ] 이다.

위의 공식이 어떻게 적용되는지 조금만 구체적으로 알아보자.

현재 Index번호가 위에서 했던 예시처럼 '9'라고 가정해보자. 9 = 1001(2) 이다. 여기서 우리는 빨강색 '1'을 찾기 위한 연산을

진행할 것이다.

먼저, '-Index번호' 라는 것은, 현재 값에 대해서 2의보수 값을 나타낸 것으로 생각할 수 있다.

2의 보수 라는 것은, "현재 값을 뒤집은 후에, 1을 더한 값" 으로 구할 수가 있다.

즉, 1001(2) 에 대한 2의 보수값을 구해보면 1001(2) → 0110(2) → 0111(2) 이 된다. 즉, -Index번호 라는 것은 0111(2)를

의미하는 것이다. 그리고 & 연산을 진행해보자. 1001(2) & 0111(2) 를 하게 되면 !! 0001(2) 이 나오게 된다.

정말 신기하게도, 저기서 나온 '1'은 원래의 숫자인 1001(2) 에서 우리가 찾는 '1이 존재하는 최하위 비트'를 의미한다.

즉, " Index번호 & -Index번호 " 의 연산이 우리에게 주는 결과값은 "우리가 찾는 '1'이 존재하는 최하위 비트" 를 알려주는 것이다.

그 후, 원래의 Index번호와 해당 결과값을 더해보자.

1001(2) + 0001(2) = 1010(2) 이 된다. 정말 신기하게도, 9번 Index다음번에 영향을 받는 10번 Index가 나오게 된다.

10번 Index에서부터도 한번 더 진행해보자.

10 = 1010(2) 이다. -Index번호를 구하기 위해서 '2의 보수'를 구해보면, 1010(2) → 0101(2) → 0110(2) 가 된다.

그리고 & 연산을 진행해보자. 1010(2) & 0110(2) = 0010(2) 가 된다. 마찬가지로 ! 결과값으로 나온 비트에서 유일하게

존재하는 '1'은 원래의 숫자인 1010(2)에서 '1이 존재하는 최하위 비트'의 위치를 가르쳐 주고 있다.

이 후 더해보면 1010(2) + 0010(2) = 1100(2) 가 되고, 1100(2) = 12 로써, 10번 Index다음에 영향을 미치는 Index번호는

12번 Index라는 것을 우리에게 가르쳐주고 있다.

위와 같은 연산을 통해서 굉장히 간편하게 구할수가 있다. 코드를 보면 훨씬 더 놀랄 것이다. 아래는 소스코드이다.

void Update(int Idx, int Value)
{
    while (Idx < Fenwick_Tree.size())
    {
        Fenwick_Tree[Idx] = Fenwick_Tree[Idx] + Value;
        Idx = Idx + (Idx & -Idx);
    }
}

이게 펜윅트리에서 생성할 때도 사용하는 부분이고, 특정 배열의 값을 변경하는 연산 때문에 펜윅트리의 상태를 변경할 때도

사용하는 코드이다.

line3)에서 보면, Index번호가 펜윅트리의 크기를 넘지 않는 선에서 계속해서 반복한다.

line5)에서 보면, 펜윅트리의 업데이트가 발생하는데, 연산에 의해서 나오는 Index번호들은 실제로 펜윅트리에서 해당 Index에

의해 영향을 받는 Index들만 발생하게 된다.

line6)을 보면, 우리가 위에서 했던 연산이다. 현재 Index번호 + ('1'이 존재하는 최하위 비트) ! 이 연산을 위와 같이 정말

간편하게 구현할 수가 있다.

void Make_PenwickTree()
{
    for (int i = 1; i <= N; i++)
    {
        Update(i, Arr[i]);
    }
}

이 코드는 위에서 말했던 펜윅트리를 생성하는 코드이다.

두 번째 연산은 "구간에 대한 연산"을 진행해보자. 가장 간편하게 "구간에 대한 합"을 계산하는 것으로 계산을 해보자.

예를 들어서 1번 ~ 7번 Index 까지의 합을 구하세요 ! 라는 입력이 주어졌다고 가정해보자.

이 그림에서 1번 ~ 7번 Index까지의 합을 구하기 위해서는 다음 노드들을 계산해줘야 한다.

위에서 색칠한 Index들을 보자. 4번Index, 6번 Index, 7번 Index를 모두 더하게 되면

4번 Index = Arr[1] + ~ + Arr[4]

6번 Index = Arr[5] + Arr[6]

7번 Index = Arr[7]

의 값을 가지고 있으므로 1 ~ 7번 Index의 구간합을 구할 수 있게 된다.

지금부터는 역순으로 가는 방법을 생각해볼 것이다. 앞에서 특정 값을 변경하거나 Update하는 연산에서는 언급은 안했지만

"점차적으로 Index번호가 증가하는 특징" 이 있었다. 예를 들면 9번 Index의 값을 갱신하면서 영향을 받은 인덱스들은

{ 9, 10, 12, 16 } 으로 9보다 크거나 같은 인덱스들에만 영향을 미치게 되었었다. 하지만 ! 지금부터는 역순으로

작아지는 방법으로 갈 것이다.

그럼 7 → 6 → 4 로 가는 방법에 대해서 이야기해보자. 일단 모르겠으니, 비트로 표현부터 해보자.

0111(2) → 0110(2) → 0100(2) 이렇게 가야한다는 이야기인데... 어쩌면 규칙이 보였을 수도 있을 거라 생각한다.

Update하는 과정에서는 "'1'이 존재하는 최하위 비트를 찾아서, 해당 비트에 '1'을 더해주는 연산"을 진행했다면,

이번에는 반대로 "'1'이 존재하는 최하위 비트를 찾아서, 해당 비트에 '1'을 빼주는 연산"을 진행하면 된다.

0111(2) 에서 '1'이 존재하는 최하위 비트는 빨강색으로 표시된 비트이고 '1'을 빼줘보자.

0111(2)

-    1

ㅡㅡㅡㅡ

0110(2) 가 된다. 놀랍게도 그 다음 우리가 필요로 하는 Index번호인 6번 Index가 나오게 되었다.

한번 더 진행해보자. 0110(2)에서 '1'이 존재하는 최하위 비트는 빨강색으로 표시된 비트이고, '1'을 빼줘보자.

0110(2)

-  1

ㅡㅡㅡㅡ

0100(2) 가 된다. 우리가 그 다음으로 찾는 '4번 index' 가 나오게 된다.

한번 더 빼준다면 0000이 될 것이고, 0000에 대해서는 더 이상의 연산이 불가능하므로 연산을 끝내주면 된다.

즉, " 해당 Index까지의 누적합 = 현재 Index번호 - (현재 Index번호 & -현재 Index번호) " 가 된다.

그런데 ! 우리가 놓친 것이 하나 있다. 위의 파랑색 글씨에서도 알 수 있지만, '누적합' 이라는 말을 사용했다.

우리가 구하고자 하는 것은 '구간합'이다.. 예시를 한번 바꿔보자.

1번 ~ 7번Index까지의 합이 아닌 ! 3번 ~ 7번 Index까지의 합을 구해봐라 ! 라는 연산으로 바꿔보자.

그럼 먼저 어느 노드들을 계산을 해야하는지 색깔부터 칠해보자.

그림을 보고 있으니... 정확하게 3번 Index부터 7번 Index까지의 합은 구하기 힘들어 보인다.

왜냐하면 처음에 말했듯이 펜윅트리는 "누적합을 이용하는 원리" 를 가지고 있기 때문이다.

즉, 3번 Index ~ 7번 Index의 합을 구하기 위해서는 4번 Index + 6번 Index + 7번 Index - 2번 Index 를 해야 한다는 것을

확인할 수 있다. 즉, 파랑색 노드들을 모두 더하고, 노랑색 노드만큼을 빼줘야 한다 ! 왜냐하면

4번 Index = Arr[1] + Arr[2] + Arr[3] + Arr[4]

6번 Index = Arr[5] + Arr[6]

7번 Index = Arr[7]

2번 Index = Arr[1] + Arr[2]

를 가지고 있기 때문에 ! 4번 + 6번 + 7번 - 2번 을 하게 되면 Arr[3] ~ Arr[7] 에 대한 구간합을 구할 수 있게 된다.

즉 !펜윅트리에서 "A번 Index부터 B번 Index까지의 합을 구하세요 !" 라는 명령이 떨어진다면, 2번을 계산해줘야 한다.

1. B번 인덱스 까지의 누적합.

2. A - 1번 인덱스 까지의 누적합.

왜냐하면, B번 인덱스 까지의 누적합 에는 1번 ~ A - 1번 까지의 합도 포함되어 있기 때문에 그 만큼을 감소시켜 줘야 한다는

것이다 !

이 부분 역시 소스코드로 보게 되면 너무나도 간단하다.

int Sum(int Idx)
{
    ll Result = 0;
    while (Idx > 0)
    {
        Result = Result + Fenwick_Tree[Idx];
        Idx = Idx - (Idx & -Idx);
    }
    return Result;
}

소스코드에 대한 설명은 따로 하지 않겠다 !

4. 펜윅트리와 세그먼트트리

지금까지 굉장히 난이도도 있으면서 특정 분야에 있어서는 굉장히 유용한 자료구조인 펜윅트리에 대해서 알아보았다.

마지막으로 정리하는 겸 다시한번 이야기해보면, 펜윅트리는 세그먼트트리를 응용한 자료구조라고 볼 수 있다.

메모리가 훨씬 더 절약되고, 소스코드가 세그먼트 트리에 비해 간결하고 짧다는 장점을 가지고 있다.

그럼 이제부터는 세그먼트 트리는 머릿속에서 지워버리자 ! 라고 말을 할 수는 없다...

정확하게 말하자면 "펜윅트리로 구현할 수 있는 모든 문제는 세그먼트 트리로 구현할 수 있지만, 세그먼트 트리로 구현할 수

있는 모든 문제는 펜윅트리로 구현을 못할 수도 있다".

위의 예시와 같이 구간에 대한 연산과 Update하는 과정만 본다면, 펜윅트리나 세그먼트 트리나 무슨 자료구조를

사용해도 상관이 없다. 하지만 ! 구간에 대한 연산결과가 아닌, 특정 값만을 찾기를 원한다면 펜윅트리는 구현이 힘들다고 한다.

예를 들면 A번 Index부터 B번 Index 중에서의 최댓값을 찾아라 ! 혹은 최솟값을 찾아라 ! 이런 연산들이다.

1번 부터 현재 Index까지의 연산 결과를 저장하는 '누적'개념을 사용하는 펜윅트리로 위의 연산을 진행하기는 어렵다고 한다.

펜윅트리 2개를 구현함으로써 위에서 말한 '최댓값', '최솟값'을 찾는 연산을 진행할 수 있다는 이야기를 들어본 것 같아서 펜윅트리 만으로는 '최소 or 최댓값'을 찾는 연산이 완전히 불가능하다 ! 라고 말을 할 수는 없지만 펜윅트리 구조상 이런 연산들에

약한 부분이 있다고 한다.

따라서, 세그먼트 트리에 비해서 더 응용된 자료구조 이긴 하지만, 펜윅트리는 안되고 세그먼트 트리는 되는 문제들이

존재한다고 한다. 따라서 ! 2개의 자료구조 모두 정확하게 알고 사용하면 좋을 것 같다 !