펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)란?

이전 게시물에서는 세그먼트 트리에 대해 게시물을 올렸다. (세그먼트 트리 :: http://www.crocus.co.kr/648)

이 펜윅 트리를 이해하기 위해서는 세그먼트 트리가 필요충분조건은 아니지만, 

세그먼트 트리를 먼저 공부하고 펜윅 트리를 공부하는 것을 추천한다.

펜윅 트리는 세그먼트 트리의 메모리를 더 절약하기 위해 만든 방법으로 만들어졌고 실제로 코드도 매우 간결하다.

즉, 펜윅 트리는 세그먼트 트리의 변형으로써 

update O(lgN)에 그리고 query를 O(lgN)에 수행 할 수 있으며 메모리는 세그먼트 트리에 비해 덜 소모된다는 것이다.

펜윅 트리의 핵심은 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료 구조를 만들어도 구간 합을 계산할 수 있다는 것이다.

(이때 부분 합은 0~k까지 합이고 구간 합은 a~b까지 합을 의미한다.)

자세한 내용은 아래에서 확인해보자.

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)와 세그먼트 트리(Segment Tree)

펜윅 트리와 세그먼트 트리가 어떻게 다른지 알아보자.

세그먼트 트리로 다음과 같이 되어있다고 보자.

이 세그먼트 트리를 펜윅 트리로 변형하면 아래와 같은 그림의 형식으로 변한다. 

이 그림을 다음과 같이 변형 할 수 있다.

위의 트리 그림과 아래 도식화 그림이 같다는 느낌으로 다가온다면 지금부터 펜윅 트리의 진가를 알 수 있게 된다.

우선 펜윅 트리는 비트를 가지고 놀기 때문에 인덱스를 0번부터가 아닌 1번부터로 바꾸어준다.(코드에서 +1만 하면된다.)

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 동작 방식

펜윅 트리 업데이트 방식

만약 1번 인덱스의 값을 5로 변경(update)하면 펜윅 트리에서 어떤 부분이 변경되어야 할까?

다음과 같이 1의 값을 5로 update 했다면 1, 1-2, 1-4, 1-8, 1-16의 부분을 업데이트 해주면 된다.

만약 7번 인덱스의 값을 9로 변경(update)하면 펜윅 트리에서 어떤 부분이 변경되어야 할까?

다음과 같이 7의 값을 9로 update 했다면 7, 1-8, 1-16의 부분을 업데이트 해주면 된다.

만약 15번 인덱스의 값을 2로 변경(update)하면 펜윅 트리에서 어떤 부분이 변경되어야 할까?

펜윅 트리 구간 합 방식

만약 인덱스 5~15번 사이의 구간합을 구하고 싶다면 어떻게 해야 할까?

다음과 같이 (1-8) + (9-12) + (13-14) + (15) - (1-4)를 하면 5-15의 구간합을 얻을 수 있다.

만약 인덱스 1~7번 사이의 구간합을 구하고 싶다면 어떻게 해야 할까?

다음과 같이 (1-4) + (5-6) + (7)을 하면 1-7의 구간합을 구할 수 있다.

이러한 방식으로 펜윅 트리는 동작하게 된다.

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)의 비트 방식으로 바라보기

펜윅 트리의 마지막 값들을 비트로 나타내면 다음과 같다.

다시한번 5~15의 구간합을 나타내보면 다음과 같다.

이때 비트를 자세히 보면 다음과 같은 현상이 일어난다.

8 + 12 + 14 + 15를 할 때 1000 + 1100 + 1110 + 1111이라는 비트로 바뀌는데

1111 -> 1110 -> 1100 -> 1000으로 바뀌는 것을 확인 할 수 있다.

즉, 1이 있는 가장 오른쪽(최하위 비트)가 0으로 바뀌는 모습을 볼 수 있다.

또다른 1~13의 구간합을 나타내보면 다음과 같다.

1101 + 1100 + 1000을 보면 1101에서 1이 빠져서 1100이 되고 1100에서 1이 빠져서 1000이 된다.

이러한 방식으로 합을 진행한다.

그렇다면 업데이트는 어떻게 진행될까?

그림을 모두 생략하고 자세히 보면 1이 있는 가장 오른쪽 최하위 비트에 1을 더해가면 update가 가능하다.

7을 업데이트 한다 생각하면 업데이트 구간이

7(111) -> 8(1000) -> 16(10000)이다.

111에  1을 더하면 1000이 되고, 1000에 1을 더하면 10000이 된다.

이제 펜윅 트리 소스 코드를 보면서 확인해 보자.

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 소스 코드

(( [2042번] 구간 합 구하기 :: http://www.crocus.co.kr/649 문제에 펜윅 트리를 접목한 소스 코드로 설명하겠습니다. ))

#include <cstdio>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
ll sum(vector<ll> &tree, int i)
{
    ll ans = 0;
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i); // 최하위 비트 지우기 
    }
 
    return ans;
}
 
void update(vector<ll> &tree, int i, ll diff)
{
    while (i < tree.size())
    {
        tree[i] += diff;
        i += (i & -i);
    }
}
 
int main()
{
    int n, m, k;
 
    scanf("%d %d %d", &n, &m, &k);
 
    vector<ll> arr(n + 1);
    vector<ll> tree(n + 1);
 
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
        update(tree, i, arr[i]);
    }
 
    m += k;
 
    while (m--)
    {
        int num;
        scanf("%d", &num);
 
        if (num == 1)
        {
            int index;
            ll val;
            scanf("%d %lld", &index, &val);
 
            ll diff = val - arr[index];
            arr[index] = val;
 
            update(tree, index, diff);
        }
 
        else if (num == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
 
            printf("%lld\n", sum(tree, right) - sum(tree, left - 1));
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

ll sum(vector<ll> &tree, int i)

ll sum(vector<ll> &tree, int i)
{
    ll ans = 0;
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i); // 최하위 비트 지우기 
    }
 
    return ans;
}

부분 합을 구하는 코드를 보자. (아까도 말했듯이 부분 합은 구간 합과 다르고 부분 합은 0~k까지의 합을 구하는 것이다.)

ans += tree[i];는 해당 tree배열에 있는 값을 ans에 더하는 과정이다.

i -= (i & -i)가 핵심 코드인데 이 코드는 다음과 같이 동작한다.

   /*
        :: 원리 :: 
        1100이 있다고 생각하자 1100의 2의 보수는 0011에서 + 1을 한 0100이다,
        결국 1100은 val이고 0100은 -val이다.
        이 두개를 & 연산을 하게 된다면 0100이 되는데 이때 1은 최하위 비트 위치를 의미하고 있다.
        위의 예시를 이용하여 일반적인 식을 도출하면 (val & -val)을 이용하면 최하위 비트를 구할 수 있다. 
    */
    val = 12; // 1100
    int first = (val & -val);
 
    cout << "최하위 비트 값 :: " << first << endl;

다음 게시물에서 더 많은 비트 연산자에 관한 내용을 확인할 수 있다. http://www.crocus.co.kr/592

즉, i & -i의 의미는 어떤 값에서 1이 나타나는 최하위 비트를 알려주는 역할을 하게 된다.

결국 i -= (i & -i)이라 함은 i에서 1이 나타나는 최하위 비트를 빼준다는 것을 의미하게 되고

부분 합에서 다음 더해야 할 부분으로 향하는 것을 알 수 있다.

i -= (i & -i)의 과정이 느껴지는가?

1101에서 1100이되고 1000이 되어 부분 합을 구해준다.

void update(vector<ll> &tree, int i, ll diff)

void update(vector<ll> &tree, int i, ll diff)
{
    while (i < tree.size())
    {
        tree[i] += diff;
        i += (i & -i);
    }
}

반대로 update에서 i+= (i & -i)는 다음과 같은 의미이다.

i에서 1이 나타나는 최하위 비트에 1을 더해준다는 의미가 된다.

아래 그림을 보면 확실히 알 수 있다.

101 -> 110 -> 1000 -> 10000

이렇게 펜윅 트리에 대한 설명이 끝이났다.

세그먼트 트리는 쿼리를 구하는 데 빠른 속도를 자랑하며 신선한 충격을 줬다면

펜윅 트리는 세그먼트 트리를 변신시켜버린 것에 처음 배우는 입장에서 또 다른 충격을 줄 듯 하다. 

이 펜윅트리 설명이 부족하다고 느껴진다면 https://www.acmicpc.net/blog/view/21 에서도 펜윅 트리를 자세히 알 수 있다.